Heaps and priority queues

A heap maintains one guarantee — the extremum is at the root — and it is exactly that weakness that makes it cheap. This guide separates the heap invariant from sorted order, works through the array layout and the two sift directions, and derives the linear-time heapify that repeated insertion misses. It then covers the patterns heaps exist for: the size-k heap for top-k queries and why it must be inverted, the two-heap running median, k-way merges, and the priority queue at the centre of Dijkstra and Prim including the decrease-key problem and the stale-entry technique that replaces it. The last section is operational — bounded capacity, starvation under strict priority, and why oldest-item age is the metric that reveals it.

the heap invariant

A binary heap guarantees only that each node is at least as extreme as its children, which is far weaker than sorted order.

The invariant is enough to keep the extremum at the root and to restore it after a change in logarithmic time, and it is deliberately no stronger.

Only the root is guaranteed; the underlying list is not sorted.

import heapq
h = [5, 3, 8, 1]
heapq.heapify(h)
h            # [1, 3, 8, 5] - a valid heap, plainly not sorted
h[0]         # 1, the only position with a guarantee

Interview trap. Assuming a heap's underlying array is sorted, or that iterating it yields sorted order, is wrong — only the root is guaranteed.

Engineering practice. Read the extremum from the root, and if the whole ordering is needed, sort or drain the heap explicitly.

the array layout

A binary heap is stored in a flat array with no pointers, using index arithmetic for parent and child relationships.

A node at index i has children at 2i+1 and 2i+2 and a parent at (i-1)/2, which keeps the structure contiguous and cache-friendly.

Index arithmetic, no pointers - fix the convention once.

parent = lambda i: (i - 1) // 2      # zero-based
left,  right = lambda i: 2 * i + 1, lambda i: 2 * i + 2
# One-based instead: parent i//2, children 2i and 2i+1. Mixing them corrupts silently.

Interview trap. The arithmetic differs between zero-based and one-based conventions, and mixing them produces a structure that silently violates the invariant.

Engineering practice. Fix the convention in one place, derive both directions from it, and assert the invariant over the array in tests.

sift-up and sift-down

Insertion sifts a new element up from the end, and extraction moves the last element to the root and sifts it down.

Each operation walks one root-to-leaf path, so both are logarithmic in the element count.

Insertion sifts up from the end; extraction sifts the last element down from the root.

heapq.heappush(h, v)     # append, then sift up: O(log n)
heapq.heappop(h)         # take root, move last to root, sift down: O(log n)

Interview trap. Sifting down after an insertion, or up after an extraction, leaves the invariant broken in a way that only shows up several operations later.

Engineering practice. Match the direction to where the violation is — at the end for insertion, at the root for extraction — and test the invariant after every operation.

linear-time heapify

Building a heap from an existing array takes linear time, not linearithmic.

Sifting down from the last internal node to the root does work proportional to each node's height, and the sum of heights over a complete tree is linear in the node count.

Building from a list is O(n); pushing one at a time is O(n log n).

import timeit
setup = "import heapq, random; a = [random.random() for _ in range(1_000_000)]"
timeit.timeit("heapq.heapify(a[:])", setup, number=5)                       # ~0.16s
timeit.timeit("h=[]\nfor v in a: heapq.heappush(h, v)", setup, number=5)    # ~0.32s

The sum of node heights is O(n), which is why sifting down from the last internal node is linear.

Interview trap. Building by repeated insertion costs O(n log n), which is asymptotically worse and easy to write by accident.

Engineering practice. Use the library's heapify when the whole collection is available up front, and quote the linear bound with the sum-of-heights argument.

min-heaps and max-heaps

A library usually provides one direction only, and the other is obtained by negating keys or supplying a reversed comparator.

Negation works for numeric keys and fails for keys that are not negatable, where a comparator or a wrapper type is required.

Python gives a min-heap; negate numbers or push a comparison key.

heapq.heappush(h, -value)          # max-heap by negation
value = -heapq.heappop(h)

# Negation is unsafe for a fixed-width minimum; in Python it is exact, but a
# tuple key (rank, seq, payload) is clearer and works for non-numeric orders.

Interview trap. Negating floating-point keys is safe, but negating a minimum integer value overflows in fixed-width languages.

Engineering practice. Prefer an explicit comparator when the language supports one, and reserve negation for bounded numeric keys.

the top-k pattern

The k largest elements are found with a heap of size k, in O(n log k) time and O(k) space.

The heap holds the current best k with the weakest at its root, so each new element is compared against the root and either discarded or swapped in.

A min-heap of size k, so the weakest candidate is the one exposed for eviction.

h = []
for v in stream:
    heapq.heappush(h, v)
    if len(h) > k: heapq.heappop(h)     # drops the smallest - the wrong one to keep
# h now holds the k largest. O(n log k) time, O(k) space.

Interview trap. Using a max-heap for the k largest is the standard inversion error: the heap must be a min-heap so the weakest candidate is the one exposed for eviction.

Engineering practice. Choose the heap direction so the element to evict sits at the root, and state the bound as O(n log k) rather than O(n log n).

top-k versus sorting versus selection

Sorting gives the k largest in O(n log n), a heap in O(n log k), and quickselect in expected O(n), and the right choice depends on k and on whether the result must be ordered.

Quickselect partitions rather than orders, so it gives the k largest as an unordered set with a worst case that is quadratic unless the pivot is chosen carefully.

For k = 10 out of 1,000,000 the heap does 10x fewer comparisons than a sort.

Method	Time	Space	Result order
sorted(a)[-k:]	O(n log n)	O(n)	sorted
size-k heap	O(n log k)	O(k)	unordered
heapq.nlargest(k, a)	O(n log k)	O(k)	sorted
quickselect	O(n) expected	O(1)	unordered

Interview trap. Claiming the heap is always best ignores that for k close to n a full sort is simpler and comparable, and that quickselect wins when order is not needed.

Engineering practice. Pick from k's magnitude and the ordering requirement, and name the worst case when proposing quickselect.

streaming medians

Two heaps — a max-heap of the lower half and a min-heap of the upper half — maintain a running median in logarithmic time per element.

Each insertion goes to the appropriate side and then the sizes are rebalanced so they differ by at most one, which keeps the median at one or both roots.

Two heaps, rebalanced after every insertion.

lo, hi = [], []      # lo is a max-heap by negation, hi a min-heap
def add(v):
    heapq.heappush(lo, -heapq.heappushpop(hi, v))
    if len(lo) > len(hi): heapq.heappush(hi, -heapq.heappop(lo))
def median():
    return hi[0] if len(hi) > len(lo) else (hi[0] - lo[0]) / 2

Interview trap. Failing to rebalance after every insertion lets one side grow, and the reported median then drifts away from the true one.

Engineering practice. Rebalance unconditionally after each insertion, and test with sorted, reverse-sorted, and alternating inputs.

merging sorted sequences

Merging k sorted sequences with a heap of their heads costs O(n log k) rather than the O(nk) of repeated linear scans.

The heap holds one candidate per sequence, and each extraction is followed by pushing the next element of the sequence that produced it.

Hold one element per sequence: O(n log k), memory O(k).

import heapq
list(heapq.merge(*sorted_lists))     # lazy, holds k heads

# Pushing everything into one heap is also correct and holds all n elements.

Interview trap. Pushing the whole of each sequence into one heap works but uses memory proportional to the total rather than to k.

Engineering practice. Hold one element per sequence, and store the sequence identity alongside the value so the replacement can be found.

priority queues in graph algorithms

Dijkstra's algorithm and Prim's algorithm are both a heap plus a relaxation rule, and the heap is what makes them efficient.

The heap always exposes the unfinished vertex with the smallest tentative distance, which is exactly the vertex whose distance is now final.

The extracted minimum is final, which is the whole correctness argument.

while pq:
    d, u = heapq.heappop(pq)
    if u in done: continue        # stale entry
    done.add(u)                   # d is now the final distance to u
    for v, w in adj[u]:
        if v not in done: heapq.heappush(pq, (d + w, v))

Interview trap. Substituting a linear scan for the heap keeps the algorithm correct but changes the complexity from near-linearithmic to quadratic.

Engineering practice. Use the heap, and be able to state why extracting the minimum makes that vertex's distance final.

the decrease-key problem

Binary heaps do not support decreasing a key in place without an index map, which shapes how Dijkstra is written in practice.

The usual workaround pushes a new entry and ignores stale ones on extraction, which costs extra memory but avoids maintaining positions.

Push a better entry and skip stale ones; binary heaps have no decrease-key.

# The heap may hold several entries per vertex - up to E of them.
# Memory is O(E) rather than O(V), which is the price of not maintaining positions.
if u in done: continue

Interview trap. Forgetting to skip stale entries makes the algorithm process a vertex twice, which can produce wrong answers with certain tie-breaking.

Engineering practice. Record finalised vertices and skip stale heap entries on extraction, or maintain an explicit position map if memory is tight.

lazy deletion

Arbitrary removal from a heap is not supported, so removal is usually simulated by marking and skipping.

The heap can grow beyond the live element count, so the memory bound becomes the number of insertions rather than the number of live entries.

The heap grows with insertions, not with live entries.

h, live = [], {}
def remove(task): live[task] = False        # marked, not removed
def pop():
    while h and not live[h[0][1]]: heapq.heappop(h)
    return heapq.heappop(h)

Rebuild when the stale fraction gets large, or the memory bound is the insertion count.

Interview trap. Assuming the heap's size equals the live set breaks any capacity reasoning built on it.

Engineering practice. Track the live count separately, and periodically rebuild the heap when the stale fraction becomes large.

heapsort

Heapsort sorts in O(n log n) worst case with constant extra space, and is still rarely the fastest choice in practice.

It heapifies in place and then repeatedly swaps the root to the end, but its access pattern jumps across the array and defeats the cache.

Same worst case as introsort, worse cache behaviour.

def heapsort(a):
    heapq.heapify(a)
    return [heapq.heappop(a) for _ in range(len(a))]

CPython's sorted is Timsort: O(n log n) worst case and far faster on real data, because it exploits existing runs and stays cache-friendly.

Interview trap. Choosing heapsort for its worst-case bound without measuring usually costs throughput against an introsort that has the same guarantee.

Engineering practice. Use the library sort, which typically switches to heapsort only as a fallback to bound quicksort's worst case.

stability and ties

A heap is not stable, so equal-priority elements come out in an unspecified order.

Adding a monotonically increasing sequence number as a tiebreaker restores first-in-first-out behaviour among equal priorities.

Add a sequence number, or equal priorities come out in an unspecified order.

import itertools
counter = itertools.count()
heapq.heappush(pq, (priority, next(counter), task))    # FIFO among equals

Interview trap. Relying on observed tie order produces a system whose behaviour changes when the element count crosses a resize boundary.

Engineering practice. Add an explicit tiebreaker when the order among equals matters, and make it part of the comparison key.

comparing non-comparable payloads

When heap entries are tuples of priority and payload, a tie on priority forces a comparison of the payload, which may fail or be meaningless.

A unique tiebreaker between priority and payload guarantees the payload is never reached by the comparison.

Without a tiebreaker, a priority tie compares the payload and raises.

heapq.heappush(pq, (1, {"id": "a"}))
heapq.heappush(pq, (1, {"id": "b"}))    # TypeError: '<' not supported between dicts

The failure appears only when two priorities happen to be equal, which is why it reaches production.

Interview trap. Pushing tuples of priority and an arbitrary object raises an error at an unpredictable moment — only when two priorities happen to be equal.

Engineering practice. Always insert a unique sequence number as the second element, so payload comparison never occurs.

d-ary heaps

Increasing the branching factor makes insertion cheaper and extraction more expensive, and improves cache behaviour.

A four-ary heap has a shallower tree, so sift-up is shorter, while sift-down must compare more children per level.

Shallower tree: cheaper sift-up, more comparisons per sift-down.

Branching	Height at n = 10^6	Sift-up	Sift-down
2	20	20 swaps	20 x 1 comparison
4	10	10 swaps	10 x 3 comparisons

Dijkstra pushes far more than it pops, which is why a 4-ary heap often measures faster.

Interview trap. Assuming binary is optimal ignores that decrease-key-heavy workloads such as Dijkstra often measure faster with a higher branching factor.

Engineering practice. Default to the library's binary heap, and consider a wider heap only with a measurement showing sift-up dominance.

Fibonacci heaps in theory and practice

Fibonacci heaps improve the asymptotic bound for decrease-key to amortised constant time and are almost never faster in practice.

Their constant factors and pointer-heavy layout outweigh the asymptotic gain except on very large, very dense graphs.

Better bound, worse constants - rarely the practical choice.

Heap	decrease-key	Dijkstra bound	In practice
Binary	O(log n)	O((V + E) log V)	fastest for most graphs
Fibonacci	O(1) amortised	O(E + V log V)	wins only on very dense graphs

Interview trap. Quoting the Fibonacci-heap bound for Dijkstra as the practical complexity misrepresents what real implementations do.

Engineering practice. State the binary-heap bound as the practical one, and mention the Fibonacci bound as a theoretical improvement.

bounded heaps and backpressure

A priority queue over untrusted input needs a capacity bound, or it becomes an unbounded memory sink.

Bounding requires a policy for what to drop — the lowest priority, the oldest, or the incoming item — and that policy is a product decision.

Set a capacity and a drop policy, or overload becomes an out-of-memory kill.

if len(pq) >= CAPACITY:
    dropped.inc()
    if priority <= pq[0][0]: return        # refuse the new item (larger priority wins)
    heapq.heapreplace(pq, entry)           # or evict the lowest priority

Interview trap. Leaving the queue unbounded moves an overload condition into an out-of-memory failure that takes the whole process down.

Engineering practice. Set a capacity, choose the drop policy deliberately, and expose the drop count as a metric.

priority inversion and starvation

A strict priority queue starves low-priority work indefinitely whenever high-priority work keeps arriving.

Ageing — increasing an item's effective priority with its waiting time — bounds the starvation while keeping the ordering broadly intact.

Age the priority, or low-priority work never runs under sustained load.

effective = base_priority - (now - enqueued_at) / AGING_SECONDS

With strict priority and a steady stream of high-priority work, the low-priority queue depth can stay flat while its oldest item is hours old.

Interview trap. Treating starvation as a load problem rather than a design property of strict priority leads to capacity increases that do not fix it.

Engineering practice. Add ageing or a reserved share for low-priority work, and monitor the oldest item's age rather than only the queue depth.

the oldest-item metric

Queue depth alone does not reveal a stuck priority queue; the age of the oldest item does.

A queue can hold a steady depth while a particular class of item never leaves, which depth-based alerting cannot see.

Depth looks healthy while one class never leaves.

oldest_age_seconds = now - min(entry.enqueued_at for entry in pq)
# Alert on this per priority class, not only on len(pq).

Interview trap. Alerting only on depth misses starvation entirely, which is the failure mode priority queues actually have.

Engineering practice. Emit oldest-item age per priority class, and alert on it alongside depth.

concurrent priority queues

A concurrent priority queue serialises at the root, which makes it a contention point under load.

Every extraction touches the root, so lock-based implementations scale poorly and lock-free ones are difficult to get right.

Every extraction touches the root, which serialises the whole structure.

# Sharding by priority band keeps contention down and loses the global order:
shard = shards[priority_band(p)]      # approximate ordering, decided deliberately

Interview trap. Sharding the queue by priority breaks the global ordering, which may or may not be acceptable and must be decided rather than assumed.

Engineering practice. Shard when approximate ordering is acceptable, and measure contention before choosing a lock-free implementation.

heaps versus balanced trees

A heap gives the extremum cheaply; a balanced tree gives the extremum, ordered iteration, and arbitrary deletion, at a higher constant factor.

If the workload needs to remove specific elements or scan in order, the tree's extra capability is worth its cost.

A heap cannot remove an arbitrary element; a tree can.

Operation	Heap	Ordered tree
peek extremum	O(1)	O(log n)
pop extremum	O(log n)	O(log n)
remove arbitrary	O(n)	O(log n)
ordered iteration	O(n log n)	O(n)

Interview trap. Reaching for a heap and then needing arbitrary removal leads to the lazy-deletion workaround and its unbounded growth.

Engineering practice. Choose the tree when removals are not extremum-only, and the heap when they are.

peek, pop, and the empty case

The empty heap is a real state that every consumer must handle, and different libraries signal it differently.

Some raise, some return a sentinel, and some have undefined behaviour, so the contract has to be read rather than assumed.

Libraries disagree on what an empty pop does; read the contract.

heapq.heappop([])          # IndexError
# Java: PriorityQueue.poll() returns null, remove() throws.
# C++: std::priority_queue::pop() on empty is undefined behaviour.

Interview trap. Assuming a heap is non-empty because the producer is running is a race, not an invariant.

Engineering practice. Check emptiness explicitly or use the library's non-throwing variant, and decide what an empty queue means to the caller.

complexity summary

Insertion and extraction are logarithmic, peek is constant, and construction from a collection is linear.

Search for an arbitrary element is linear, which is why the structure supports no efficient membership or removal query.

Constant peek, logarithmic push and pop, linear build - and linear search.

Operation	Cost
peek	O(1)
push / pop	O(log n)
heapify a list	O(n)
membership / arbitrary removal	O(n)

Pair the heap with a set when membership matters.

Interview trap. Assuming a heap can answer membership cheaply because it is a tree confuses the heap invariant with the search-tree one.

Engineering practice. Pair the heap with a hash set when membership queries are needed, and keep the two in sync at the boundary.

recognising a priority-queue problem

A heap is the right structure whenever the algorithm repeatedly needs the most extreme remaining item and the set keeps changing.

Sorting is better when the set is fixed, a hash structure is better when the query is membership, and a tree is better when removal is arbitrary.

Repeated extremum extraction over a set that keeps changing.

# Sort: the set is fixed.
# Heap: elements arrive while you are consuming - k-way merge, Dijkstra,
#       task scheduling, streaming top-k, event simulation.

Interview trap. Sorting inside a loop over a changing collection is the usual way this structure is missed.

Engineering practice. Look for repeated extremum extraction over a mutating set, and reach for the heap when that is the shape.