Removing the minimum element from a heap
Let min(H) denote the minimum element of a heap H.
Find minimum value: Findmin(H). Easy! Return the value of the root.
Remove minimum value: Removemin(H): Trickier.
Remove the top element. Two heaps result: H1, H2.
Problem: How do you combine them into a single heap?
Suppose min(H1) < min(H2). Place min(H1) at top; its children will be H2 and Removemin(H1). A nice recursive rule.
(Other cases? What if one of Hi is empty?)
✤
✤
✤
✤
✤
✤
Removemin, in pictures
Removemin, in pictures
Removemin, in pictures
Removemin, in pictures
a