Heap removing and adding

Question

Now I have a heap or priority queue to maintain the max value of a series of numbers. Usually, if I want to pop the max value, fetching and removing the root number then putting the last number in the root and shifting down to balance; If I want to add a new number, adding the number at the end of the heap then shifting up to balance.

So my question: If I want to pop the max value and immediately add new value, could I just remove the root number and put the new one in the root then shifting down to balance? If it is wrong, why? If it is true, how to prove it?

Answer 1

I guess that this is correct because this is the standard heapify() operation.

The heapify() operation only assumes that both child trees are heap. Removing the top node does not break that very only assumption of the heapify() method. The pseudo-code for the method is shown below:

procedure heapify(H)

     if H.LeftChild > H.RightChild then

         if H.LeftChild>H.Root then

               swap(H.Root,H.LeftChild);

               heapify(H.LeftChild);

        endif

   elsif H.LeftChild <= H.RightChild then

         if H.RightChild>H.Root then

               swap(H.Root,H.RightChild);

               heapify(H.RightChild);

        endif

   endif

endprocedure

This function use recursive calls to extract the solution.

Comments

Thank you Runyu. I think that your code can work well with the removing and inserting operation in my question. But I find a small problem in your proof, in my opinion, "heapify() operation only assumes that both child trees are heap" and the total tree should be complete binary tree. In my case, the heap is always a complete binary tree.

---

yes, it should be a binary tree. but it is not necessarily complete, I guess.