Removing the top, and two fancier relatives

Extract: bubble down

The only value anyone can remove from a heap is the root — that restriction is the whole point, the same way a stack only ever exposes its top. Move the very last array element into the root's empty spot to keep the shape rule intact, then repeatedly swap it with its larger child (in a max-heap) until it settles below both its children or reaches a leaf.

This mirrors Unit II Lesson 6's BST deletion in spirit — both move a value in from elsewhere to patch a hole, then let it settle to a valid position — but a heap's fixed shape rule makes the patching mechanical rather than requiring a choice like the inorder successor.

Extract max from [50, 30, 40, 10, 20]:

1. Save 50 to return.
2. Move last element (20) to the root: [20, 30, 40, 10]
3. Bubble down: 20 < 30, swap -> [30, 20, 40, 10]
4. 20 has no children left to compare — done.

Result: returns 50, heap becomes [30, 20, 40, 10]

Where heaps actually get used

A priority queue is the direct application — a print spooler serving urgent jobs first, a hospital triage list, an operating system scheduler choosing which process runs next. Heap sort is the other classic use: build a max-heap from an array, then repeatedly extract the maximum into the end of the array, which sorts it in place without the extra memory a merge would need — a preview of Unit IV.

Binomial and Fibonacci heaps: trading simplicity for faster merges

A binary heap has one weakness: merging two of them into one takes time proportional to their combined size, because there is no cheap way to combine two complete-tree shapes. A binomial heap is built instead from a small collection of trees with a special structure, each a power-of-two in size, which allows two binomial heaps to merge quickly — closer to logarithmic than linear.

A Fibonacci heap pushes this further, allowing an even lazier structure that delays cleanup work until it is actually needed — this is what backs the fastest known versions of graph algorithms in Unit IV that repeatedly need 'give me the smallest, and let me occasionally decrease a value already inside.' Both are genuinely more complex to implement than a binary heap, which is exactly why a plain binary heap remains the default choice unless merging or decrease-key operations are frequent enough to justify the extra complexity.