minimum and maximum number of comparisons needed when deletion in Binary Min heap

Question

You are given a binary min heap of height p Let the minimum and maximum number of comparisons we might have to do when doing a delete min respectively are u and v. Then What will be the value of v-u?

Answer 1

You really should try to answer your own question before you post it here. Think of how the heap works. I won't "give" you the answer, but perhaps I can help you understand how to approach finding the answer.

Insertion into a binary heap involves adding the item at the lowest level and then sifting it up to where it needs to go. If the tree has a height h, how many levels must it move to get to the top? How many comparisons are required to move the item up one level?

Deletion in the heap is just a little bit more involved:

1. Move the last item in the heap to the top
2. Sift it down to its proper position

If the tree has a height h, how many levels must it move to get back to the leaf level? How many comparisons does it take to move one level?

That breaks the problem down into simpler pieces so you can think about it more clearly. The answer to the first question (how many levels to move) should be evident if you have any idea of how the heap works. The answer to the second question (comparisons per level) should be be evident from the description of the algorithm (or from reading the code that implements it).