views:

27

answers:

1

After removing the minimum element in a binary heap, i.e. after removing the root, I understand that the heap must be adjusted in order to maintain the heap property. But the preferred method for doing this appears to be to assign the last leaf to the root and sift it down.

I'm wondering why we don't take the lesser child of what used to be the root and just keep sifting up all the children? Isn't this the same amount of operations, so why is that "assign-the-last-leaf-to-the-root-and-sift-down" method preferred?

+4  A: 

Because you have to keep the tree filled from the left hand side on the last row. Sifting up from the top down, you can't guarantee that the last element you sift upwards will be the rightmost element.

Marcelo Cantos
Try working out a simple example like this: `[1,3,5,4,6,7]`. If you move up the lesser child you end up with a heap like: `[3,4,5,X,6,7]` (with the X being a hole). Taking the last element ends up with a heap looking like: `[3,4,5,7,6]`.
Dolphin