patternMinor
heap pop creates unbalanced tree?
Viewed 0 times
createsunbalancedheaptreepop
Problem
say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something you have to do to maintain the balance of the tree?
Solution
When popping the root, it is first replaced by the very last element, and then a heapify operation is performed to maintain the heap invariant, namely, that every node is smaller than its children.
Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.
The three steps are illustrated in the Wikipedia article. We start with a max-heap:
We remove the root, and replace it with the very last element:
Finally, we perform a heapify operation on the root:
Since we are removing the very last leaf, the heap always remains balanced, in the sense that all levels but the last will be full, and the last level will consist of a prefix of the set of potential vertices.
The three steps are illustrated in the Wikipedia article. We start with a max-heap:
We remove the root, and replace it with the very last element:
Finally, we perform a heapify operation on the root:
Context
StackExchange Computer Science Q#104235, answer score: 4
Revisions (0)
No revisions yet.