Re-adjusting a binary heap after removing the minimum element
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 assi开发者_StackOverflow中文版gn 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?
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.
精彩评论