Heaps and Priority Management

Always Serving the Most Urgent

Sometimes you need not "oldest first" (a queue) but "most important first." The priority queue ADT serves elements in order of priority rather than arrival: you insert items with priorities, and each removal returns the highest- (or lowest-) priority item. 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) that satisfies the heap property: in a max-heap, every parent is greater than or equal to its children, so the maximum sits at the root; a min-heap is the mirror, with the minimum at the root. The extreme element is therefore always available in $O(1)$ at the top.

Insertion and removal keep the heap property by "bubbling":

• Insert places the new element at the next open leaf, then sifts it up, swapping with its parent while it is larger (in a max-heap), until the property holds — $O(\log n)$, the tree's height.
• Remove-max takes the root, moves the last leaf to the root, then sifts it down, swapping with its larger child until the property holds — also $O(\log n)$.

A neat implementation detail: because the tree is complete, a heap is stored compactly in a plain array, with a node at index $i$ having children at $2i+1$ and $2i+2$ — no pointers needed. Heaps power priority scheduling, Dijkstra's shortest paths, and the $O(n \log n)$ heapsort.

Common pitfall: expecting a heap to be fully sorted. It is only partially ordered — the heap property relates each parent to its children, but siblings and cousins are unordered. A heap guarantees fast access to the single extreme element, not a sorted sequence; to get sorted output you must repeatedly remove the root.