Lots of programs need a priority queue: add items in any order, and always be able to take out the most important one next. Think of task schedulers, Dijkstra's shortest paths, event simulations, or finding the top k items. A sorted array makes inserting slow (O(n)); an unsorted one makes removing the maximum slow (O(n)). A binary heap does both in O(log n), and can show you the maximum in O(1).
That's all. Siblings can be in either order, so a heap is not sorted, just sorted enough. These pages use a max-heap; a min-heap is the mirror image (every parent ≤ its children).
Because the tree is complete, we can store it level by level in an array with no gaps and no pointers. For the node at index i:
Put the new key in the next free spot, index n, so the tree stays complete. It may be larger than its parent (P). If so, swap them, and keep swapping upward until its parent is larger or it reaches the root. That's at most one swap per level: O(log n).
The maximum is the root. Take it out, and fill the hole with the last element, the only one that can move without leaving a gap. That element is probably small, so sift it down. Compare it with its children (L and R). If either is larger, swap it with the larger child. Why the larger one? It becomes the parent of the other, so it has to be the bigger of the two. Repeat until both children are smaller, or it reaches a leaf.
| Operation | How | Cost |
|---|---|---|
| Peek at max | Read the root, index 0. | O(1) |
| Insert | Add at index n, sift up. | O(log n) |
| Extract-max | Move the last element to the root, sift down. | O(log n) |
| Build from n keys | Sift down every non-leaf, bottom-up (see Heapsort). | O(n) |