Question

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?

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top