say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something you have to do to maintain the balance of the tree?

  • 3
    $\begingroup$ Please go over your question again and try to be more precise: lists don't have roots; balancedness is not the same as completeness. Also, have you tried some examples? Have you tried proving the invariant of completeness using induction? Note that heapify always swaps with the larger child -- you'll certainly have to use that! $\endgroup$ – Raphael Feb 12 '19 at 11:56

When popping the root, it is first replaced by the very last element, and then a heapify operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.

Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.

The three steps are illustrated in the Wikipedia article. We start with a max-heap:

enter image description here

We remove the root, and replace it with the very last element:

enter image description here

Finally, we perform a heapify operation on the root:

enter image description here

  • $\begingroup$ thanks. do we have to assume that at any given level, the elements increase from left to right? $\endgroup$ – bart Feb 12 '19 at 19:54
  • $\begingroup$ No. This is not guaranteed to hold. I suggest reading a thorough account of binary heaps. $\endgroup$ – Yuval Filmus Feb 12 '19 at 19:56
  • $\begingroup$ No, that’s wrong. Run the algorithm and see what happens. $\endgroup$ – Yuval Filmus Feb 12 '19 at 19:59
  • $\begingroup$ yes, sorry. thanks for your help $\endgroup$ – bart Feb 12 '19 at 20:00
  • $\begingroup$ oh of course. the shape of the tree doesnt change, i.e. you dont add any new leaves. very silly question, but i guess i needed the picture. thank you again. $\endgroup$ – bart Feb 12 '19 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.