Heaps and Priority Management

Always Serving the Most Urgent

Sometimes you need the most important item first, not the oldest. A priority queue serves elements by priority rather than arrival. The structure that implements it efficiently is the binary heap.

A binary heap is a complete binary tree (filled level by level, left to right) satisfying the heap property:

The extreme element is always available in $O(1)$ time at the top.

Operations and Layout

Insertion and removal maintain the heap property via sifting in $O(\log n)$ time:

• Insert: Place at the next open leaf, then sift up (swap with parent while larger).
• Remove: Take root, move last leaf there, then sift down (swap with larger child).

Because the tree is complete, store it in a plain array: node $i$ has children at $2i+1$ and $2i+2$.

Common pitfall: Expecting a heap to be fully sorted. It is only partially ordered—parents relate to children, but siblings and cousins are unordered. Heaps give fast access to the extreme element, powering Dijkstra's and heapsort.