Priority Queue and Heap

Definition: A Priority Queue is an abstract data type where elements have priorities and are served highest-priority-first; a Heap (Min-Heap or Max-Heap) is the complete binary tree, implemented in a flat array, that provides O(1) top access and O(log n) insertion/deletion, and is the standard way to implement it.

How It Works

A Min-Heap maintains the invariant parent <= child at every node, so the minimum element is always at the root. A Max-Heap maintains the mirror invariant, parent >= child.

The array representation avoids pointers entirely. For a node at index i (0-indexed): the left child sits at 2i+1, the right child at 2i+2, and the parent at floor((i-1)/2). This arithmetic relationship is what makes heaps compact and cache-friendly compared to pointer-based trees, and it’s only possible because a heap is always a complete binary tree (every level full except possibly the last, filled left to right).

Insertion: append the new element at the end of the array, then repeatedly swap it with its parent while it violates the heap property, called sift-up or heapify-up. O(log n), since the element moves up at most the height of the tree.
Removal (extract root): swap the root with the last array element, shrink the array by one, then repeatedly swap the new root down with its smaller (min-heap) or larger (max-heap) child until the property holds again, called sift-down or heapify-down. Also O(log n).
Building a heap from n unsorted elements takes O(n), not O(n log n), because most nodes near the bottom of the tree need very few sift-down swaps, and only a small fraction near the root need close to log n swaps; the sum across all levels works out to a linear bound. This tighter build bound is exactly what makes HeapSort’s construction phase O(n) rather than O(n log n).

Build-Heap, Traced

Turning the unsorted array [9, 4, 7, 1, 8, 2] into a min-heap in place. build_heap only needs to sift-down starting from the last non-leaf node (index n/2 - 1 = 2) backward to the root, since leaves are trivially valid single-node heaps already:

array: [9, 4, 7, 1, 8, 2]   indices: 0=9, 1=4, 2=7, 3=1, 4=8, 5=2

sift-down idx2 (7): children idx5(2) -> 2 < 7, swap        -> [9, 4, 2, 1, 8, 7]
sift-down idx1 (4): children idx3(1), idx4(8) -> min is 1 (idx3) -> swap -> [9, 1, 2, 4, 8, 7]
sift-down idx0 (9): children idx1(1), idx2(2) -> min is 1 (idx1) -> swap -> [1, 9, 2, 4, 8, 7]
                    continue sifting 9 down: children idx3(4), idx4(8) -> min is 4 -> swap -> [1, 4, 2, 9, 8, 7]

Only 3 outer sift-down calls were needed (one per internal node), not 6 insertions each costing up to O(log n); that’s the concrete reason build_heap is O(n) rather than O(n log n).

Complexity Analysis

Operation	Time
Peek min/max	O(1)
Insert	O(log n)
Extract min/max	O(log n)
Build heap from n elements	O(n)
Search for arbitrary element	O(n)
Space	O(n)

Why It Matters

Essential for Dijkstra Algorithm’s shortest-path algorithm, A* search, task and job schedulers that must always run the highest-priority ready item next, and event-driven simulations ordered by timestamp.
HeapSort derives directly from the heap structure: build a max-heap in O(n), then repeatedly extract the max in O(log n) each, giving a guaranteed O(n log n) in-place sort with no worst-case degradation, unlike QuickSort’s O(n^2) worst case.
Bounded priority queues, keeping only the top-k elements seen so far, let you find the k largest or smallest items in a huge stream using only O(k) memory instead of sorting the entire dataset, a common pattern in streaming analytics.
Merging k sorted lists efficiently relies on a heap holding one candidate element per list; repeatedly extracting the minimum and pushing that list’s next element gives O(n log k) total instead of a naive O(nk) repeated-scan merge.

Common Pitfalls

Searching for an arbitrary, non-root element inside a heap takes linear O(n) time; a heap is optimized only for finding/removing the extreme element, not general lookup, so it’s a poor substitute for a hash table or BST when arbitrary search matters.
Assuming a heap is fully sorted; only the root is guaranteed to be the min/max. Sibling and cousin nodes have no defined order relative to each other, which is why an in-order traversal of a heap’s array does not produce sorted output.
Decreasing a key’s priority in place, needed for algorithms like Dijkstra that use decrease-key, isn’t supported by a plain array-backed heap without also tracking each element’s current array index externally, since the element’s position moves as the heap is modified.
Confusing a Priority Queue’s logical contract, highest priority served first, with its typical Binary Heap implementation. Fibonacci heaps and pairing heaps implement the same contract with different complexity tradeoffs, notably O(1) amortized decrease-key versus a binary heap’s O(log n).
Forgetting that “extract-min” on an empty heap is undefined behavior in most implementations; failing to check emptiness first causes an out-of-bounds access rather than a clean error.
Using a max-heap where a min-heap (or vice versa) was actually needed, an easy mix-up since both share identical structure and only differ in the single comparison direction used during sift-up/sift-down.
Assuming heap indices are 1-indexed or 0-indexed without checking; the parent/child index formulas differ slightly between conventions ((i-1)/2 for 0-indexed vs i/2 for 1-indexed), and mixing the two silently corrupts the heap property.

Comparison

	Binary Heap	Sorted Array	Unsorted Array	Fibonacci Heap
Insert	O(log n)	O(n)	O(1)	O(1) amortized
Extract min/max	O(log n)	O(1)	O(n)	O(log n) amortized
Decrease-key	O(log n), needs index tracking	O(n)	O(1)	O(1) amortized
Build from n elements	O(n)	O(n log n)	O(n)	O(n)
Space overhead	None beyond array	None beyond array	None beyond array	Pointer-heavy tree structure
Typical real-world use	General-purpose priority queue	Rarely, static datasets only	Rarely, tiny datasets only	Theoretical/decrease-key-heavy algorithms

Example

OS process schedulers use priority queues to always run the highest-priority ready process next.

Min-heap array: [2, 5, 4, 8, 9, 7]
        2
      /   \
     5     4
    / \   /
   8   9 7
insert(1): append -> [2,5,4,8,9,7,1] -> sift-up swaps 1 with 4, then with 2 -> [1,5,2,8,9,7,4]

After insert(1), the new minimum 1 rises to the root in 2 swaps, O(log n), rather than requiring a full O(n) re-sort of the array.

Extract-Min, Traced

Starting from [1,5,2,8,9,7,4] (the heap after the insert above):

array: [1,5,2,8,9,7,4]
step 1: save root (1) as the result to return
step 2: move last element (4) to the root -> [4,5,2,8,9,7]
step 3: sift-down 4: children are 5 (idx1) and 2 (idx2), smaller is 2 -> swap -> [2,5,4,8,9,7]
step 4: 4 is now at idx2, children are idx5(7) only -> 4 < 7, no swap needed -> done
return: 1

Two comparisons and one swap to restore the heap property after removing the root, O(log n) in general, matching the cost of the insertion that added the element in the first place.

Variants

Indexed / addressable heap: a heap augmented with a hash map from element to its current array index, enabling an efficient decrease_key(element, new_priority) operation without a linear search. Needed for Dijkstra’s textbook decrease-key formulation.
d-ary heap: each node has d children instead of 2, shrinking height to log_d(n) and speeding up decrease-key-heavy workloads at the cost of more comparisons per sift-down. Used in some optimized Dijkstra/Prim implementations.
Min-max heap: a single structure supporting O(log n) access to both the minimum and maximum simultaneously, useful for sliding-window median/percentile problems that need both ends at once.

Common Interview Questions

Why is build_heap O(n) and not O(n log n)? — because most nodes are near the bottom of the tree and need very few sift-down swaps; only a logarithmic fraction of nodes are near the root and need close to log n swaps.
How would you find the k largest elements in a stream? — maintain a min-heap of size k; for each new element, push it and pop the minimum if the heap exceeds size k, leaving the k largest seen so far in O(log k) per element.
Can a heap be used to implement a stack or queue? — not efficiently; a heap has no concept of insertion order, only priority order, so it can’t reproduce LIFO or FIFO semantics without an artificial priority scheme.

Real-World Systems

Linux’s kernel timer wheel and various event-loop implementations use heap-like priority queues to always fire the soonest-scheduled timer next without scanning every pending timer.
Operating system CPU schedulers implementing priority-based scheduling (as opposed to pure round-robin) commonly use a heap to select the next process to run in O(log n).
Huffman coding, used in compression formats like DEFLATE (which underlies gzip and PNG), repeatedly merges the two lowest-frequency nodes using a min-heap to build an optimal prefix-free code tree.

Referenced by

Dig deeper

Spot an error in this note?