Heaps & Priority Queues

A priority queue stores items and repeatedly returns one with extremal priority. Unlike a sorted sequence, it need not expose all items in order; unlike FIFO, insertion time does not choose removal order. A heap is a representation that keeps just enough partial order to make the extremum cheap while allowing updates without shifting a sorted array.

Specify the priority-queue contract first #

A minimum-priority queue commonly offers:

• insert(item, priority);
• min() without removal;
• extract_min();
• optionally decrease_key(handle,new_priority), arbitrary erase, and meld.

State whether equal priorities are stable, whether priorities can change, whether duplicates are allowed, and what handles survive mutation. std::priority_queue is a max-priority adaptor by default, exposes no arbitrary element handle, and does not promise stable ordering among equivalent elements. Those omissions simplify its implementation.

If equal-priority jobs must preserve arrival order, compare composite keys (priority, sequence_number). Stability is then explicit and testable. Beware counter wrap and distributed producers: the tie-breaker must remain unique and ordered within the promised scope.

A binary heap combines two invariants #

A min-heap has:

1. shape: a complete binary tree—all levels full except possibly the last, filled left to right;
2. order: every node's priority is no greater than its children's.

The order invariant implies the root is globally minimal: every root-to-node path is nondecreasing. It does not imply that siblings or subtrees are mutually sorted. Printing the array is therefore not a sorted traversal.

Completeness removes pointers. In a zero-based array, for index $i$:

$$parent(i)=\left\lfloor\frac{i-1}{2}\right\rfloor\quad(i>0),$$

$$left(i)=2i+1,\qquad right(i)=2i+2.$$

The height is $\lfloor\log_2 n\rfloor$, so repairing one root-to-leaf or leaf-to-root path takes $O(\log n)$ comparisons/swaps.

Insert swims; extraction sinks #

Insertion places the new item in the next array slot, preserving completeness, then swims it upward while it precedes its parent. Extract-min saves the root, moves the last item to the root, shrinks the array, then sinks that item by swapping with the smaller child until order is restored.

template<class T, class Less>
void swim(std::vector<T>& a, std::size_t i, Less less) {
    while (i > 0) {
        std::size_t p = (i - 1) / 2;
        if (!less(a[i], a[p])) break;
        std::swap(a[i], a[p]);
        i = p;
    }
}

template<class T, class Less>
void sink(std::vector<T>& a, std::size_t i, Less less) {
    for (;;) {
        std::size_t left = 2 * i + 1;
        if (left >= a.size()) break;
        std::size_t child = left;
        if (left + 1 < a.size() && less(a[left + 1], a[left])) ++child;
        if (!less(a[child], a[i])) break;
        std::swap(a[i], a[child]);
        i = child;
    }
}

Choosing the better child before swapping is essential. Swapping with an arbitrary violating child can leave the parent larger than the other child.

Bottom-up heap construction is linear #

Inserting $n$ elements one at a time gives an $O(n\log n)$ upper bound. Floyd/Williams bottom-up construction starts at the last internal node and sinks each internal node. Although one sink can travel $O(\log n)$, most nodes lie near leaves and travel little.

At most about $n/2^{h+1}$ nodes have height $h$, so total sink distance is bounded by

$$\sum_{h\ge 0}\frac{n}{2^{h+1}}h=O(n).$$

This is a recurring analysis lesson: multiplying “number of calls” by the worst cost of any call can be a loose bound when calls start at structurally different heights.

Heapsort reuses the representation in place #

For ascending heapsort, build a max-heap, swap the root with the last unsorted position, shrink the heap boundary, and sink the new root. Each extraction fixes one final array position. The algorithm takes $O(n\log n)$ worst-case time and $O(1)$ auxiliary storage in its array form, but it is generally unstable. Its access pattern is also less cache-friendly than highly engineered quicksort variants despite the strong worst-case bound.

More operations require more structure #

Handles and mutable priority #

decrease_key must locate the item before swimming it. Searching a plain heap array is $O(n)$, erasing the advantage. A mutable heap therefore returns handles and maintains a position map, updating that map on every swap. Define handle invalidation, generation checks, and whether priorities may both increase and decrease. A stale raw index can silently mutate the wrong item after swaps or slot reuse.

Lazy duplicate insertion is another design: insert the new (priority,id) and ignore stale records when extracted by comparing against authoritative state. This avoids mutable handles but can increase memory and extraction work. It is a different, explicit contract—not an invisible fallback.

d-ary heaps #

A $d$-ary heap shortens height to $\Theta(\log_d n)$ but a sink examines up to $d$ children per level. Larger $d$ can reduce random-access depth and help decrease-key-heavy workloads, while increasing comparisons during extraction. Choose from operation mix and measured layout, not asymptotics alone.

Meldable heaps #

A binary heap stored in one array does not meld two heaps efficiently: concatenation followed by heapify is linear in their combined size. Binomial queues represent a heap as a forest with at most one binomial tree of each rank. Meld behaves like binary addition: equal-rank trees link and carry to the next rank, giving logarithmic meld and extremum operations under the classical structure. Fibonacci and pairing heaps offer other tradeoffs, especially for theoretical or decrease-key-heavy workloads, but bring pointer, constant-factor, and implementation complexity.

Priority queues do not solve scheduling policy by themselves #

Priority scheduling raises system questions:

• Can a continuous stream of high priorities starve low priorities?
• Does priority age or inherit across dependencies?
• Are priorities trusted user input?
• Is the comparison total and deterministic?
• Can a cancelled job remain as a lazy stale heap entry indefinitely?
• Does extraction need a deadline-aware wait or batch semantics?

Multiple threads also need a compound synchronization protocol. A mutex around one heap gives simple linearizability but can bottleneck. Sharded or relaxed priority queues trade exact global-min extraction for throughput; that semantic weakening must be approved by the algorithm using it.

Review and failure diagnostics #

1. Is the root meant to be minimum or maximum, and is the comparator direction consistent?
2. Are both completeness and heap order preserved?
3. Does sink select the better child before swapping?
4. Is zero-based or one-based index arithmetic used consistently, with overflow considered for 2*i+1?
5. Is build claimed as $O(n)$ because it is bottom-up, or is it actually repeated insertion?
6. Are ties stable by contract or intentionally unspecified?
7. Does decrease-key have a validated handle/position map?
8. Are stale entries bounded and recognized against authoritative state?
9. Does the client need sorted iteration, predecessor queries, or meld—operations a basic heap does not promise?
10. Can scheduling priorities starve work or be adversarially manipulated?

Exercises #

1. Show the array after inserting priorities 7, 3, 5, 1 into a min-heap.
2. Why does a heap with root 1 and children 4 and 2 remain valid even though its breadth-first array is not sorted?
3. Explain what must happen to a position map whenever two heap elements swap.