Question

Problem 8. (Heap Top-k) Prof Dubious has made the following claim, and has provided a proof Claim. Let n and k be positive integers such that 2*-1n. In amax-heap H of n elements, the top 21 elements are in the first k layers of the heap. Proof. Since is a max-heap, each node in H must satisfy the heap property, i.e., if H, is an element of H with at least one child then Hmaxchldren(H)). We know that every subtree of the heap H is a heap, as subtrees of complete binary tro complete binary trees, and the heap property holds. Therefore since each subtree is a heap, the maximum element in each subtree must be at the root of that subtree Clearly, the largest element in H is at the root. Since the left and right subtrees are also heaps the next two largest elements must be at the root of each of these subtrees, i.e., the left and right child of the root Hence, the largest 22 - 1 3 elements of the heap lie in the first 2 layers. We repeatedly apply this argument to each subtree until we have considered the first k layers. Thus the largest 2k -1 elements in the heap must be in the first k layers. Briefly describe what is wrong with Professor Dubious's argument and provide a counter-example to their claim.

Answer 1

Most of the things in the given statement are right except the point that the top 3 elements lie in top 2 layers Top element always do lie on the root Both of its subtree contains lesser value than the root But we cannot compare amongst them and there subtrees Consider the case as shown -

6 6 1 5 3 3 2 2 4

This is a max-heap All the subtree follows max-heap property Note that subtree of 30 contains element greater than 10 (That is right subtree of 42) But top 3 3 elements are not present in top 2 layers

I have tried to explain it in very simple language and I hope that i have answered your question satisfactorily.Leave doubts in comment section if any.