POP-MIN
In this operation we need to remove the minimum priority element (the root). And then we have to fix the hole, while maintaining the heap property!
Walking Through POP-MIN
We need to remove the root of our heap, like
A Tempting but Misguided Idea…
Now, what should take its place?
Hmm…. How about 10? That's the smallest of its children.
-
Interesting. Then what would take 10's place?
-
16, I guess? And then 21…?
-
…and what's the problem?
-
We broke completeness! Now the third layer isn't full.
-
Yeah, that's an issue.
A Much Better Idea…
-
I have a suggestion. What if we protect completeness first (the structure property), then repair the heap property?
-
Okay, then I guess I'd move 68 to the root.
-
That way the tree stays complete!
-
Now we have to fix the order property…
-
Right, so we can swap with the smallest child.
-
And then keep swapping until it's in the right place.
-
Sounds good!
-
Is it complete?
-
Yup!
-
Does it satisfy the heap property?
-
Yup!
-
Then it worked!
POP-MIN Algorithm
Here is the algorithm we just developed for POP-MIN:
- Replace the root (index 0) with the last element in the heap (index n - 1).
- Swap it with its smallest child until it has a smaller key than both children.
Exercise
Starting with the tree pictured above (after popping 6), on paper, perform the POP-MIN operation again.
Then write down the level-order traversal of the resulting tree.
Here is the resulting tree:
POP-MIN Complexity
The complexity analysis of POP-MIN is pretty much just like the one for INSERT.
- We can replace the item at index 0 with the item at index \( n − 1 \) in \( \Theta(1) \) time.
- In the best case, that item can just stay at the root, in which case we take an additional \( \Theta(1) \) time.
- In the worst case, that item must sink all the way to the bottom again, which requires \( \Theta( \log{n} ) \) swaps.
So, overall, the complexity of POP-MIN is \( \mathrm{O}( \log{n} ) \).
(When logged in, completion status appears here.)