Data Structures: Heaps and Priority Queues

When software needs to repeatedly select “the next most important item,” a plain list or array quickly becomes a bottleneck. Whether you are scheduling jobs, simulating events, or running a shortest-path algorithm, you want fast access to the best candidate and efficient updates as priorities change. Heaps and priority queues are designed for exactly this: priority-based retrieval with predictable performance, typically $O(\log n)$ per insertion or removal.

This article explains binary heaps, how heapify works, how heaps enable heap sort, and why priority queues show up so often in real systems and graph algorithms.

Heaps vs. Priority Queues: What’s the Difference?

A priority queue is an abstract data type: it stores elements with priorities and supports operations like:

• Insert an element with a priority
• Find the element with the highest (or lowest) priority
• Remove the element with the highest (or lowest) priority

A heap is a common concrete implementation of a priority queue. In practice, when people say “heap,” they often mean a binary heap backed by an array.

Two standard variants:

• Min-heap: the smallest key is at the top (root)
• Max-heap: the largest key is at the top

Priority queues usually need:

• peek (top element): typically $O(1)$
• push / insert: $O(\log n)$
• pop / extract: $O(\log n)$

That combination is the reason heaps appear everywhere in performance-sensitive code.

Binary Heaps: Structure and Heap Property

A binary heap is a complete binary tree that satisfies the heap property:

• Min-heap property: every node’s key is less than or equal to its children’s keys
• Max-heap property: every node’s key is greater than or equal to its children’s keys

“Complete” matters: the tree is filled level by level from left to right, which makes it compact and easy to store in an array.

Array Representation

Binary heaps are typically stored in a 0-based array. For an element at index $i$:

• Parent index: $\lfloor (i-1)/2\rfloor$
• Left child: $2i+1$
• Right child: $2i+2$

This layout avoids pointer-heavy tree nodes, improves cache locality, and makes the implementation straightforward.

Core Operations and Why They Are $O(\log n)$

The key idea behind heap performance is that a complete binary tree has height $O(\log n)$. Insertions and removals only need to “fix” the heap along one path up or down that height.

Insertion (Push) with Sift-Up

To insert:

1. Append the new element at the end of the array (maintains completeness).
2. “Sift up” (also called bubble up): while the new element violates the heap property with its parent, swap them.

Each swap moves the element one level upward, so the number of swaps is bounded by the height: $O(\log n)$.

Extract-Min / Extract-Max (Pop) with Sift-Down

To remove the top element:

1. Save the root (the min or max).
2. Move the last element in the array to the root position.
3. Remove the last slot (array shrinks).
4. “Sift down” (heapify-down): swap the root with its best child (smaller child for min-heap, larger for max-heap) until the heap property is restored.

Again, the fix travels down at most the height of the heap: $O(\log n)$.

Peek (Find-Min / Find-Max)

Reading the root is $O(1)$ because it sits at index 0.

Heapify: Building a Heap Efficiently

If you insert $n$ items one by one, you will pay $O(n\log n)$. But when you already have an array of items, you can build a heap in linear time using heapify.

Bottom-Up Heapify (Floyd’s Method)

The standard heapify approach:

1. Treat the array as a complete tree.
2. Start from the last non-leaf node (roughly index $\lfloor n/2\rfloor -1$).
3. Sift down each node to enforce the heap property.
4. Continue backward to the root.

Although each sift-down can take $O(\log n)$ in the worst case, most nodes are near the leaves and require very little work. The total work sums to $O(n)$, which is a big win for tasks like heap sort or initializing a priority queue with many items at once.

Heap Sort: Sorting via a Heap

Heap sort uses a heap to sort an array in-place with $O(n\log n)$ time and $O(1)$ extra space (beyond the array itself). The typical approach is:

1. Heapify the array into a max-heap.
2. Repeatedly swap the root (current maximum) with the last element in the heap region.
3. Reduce the heap size by one.
4. Sift down the new root to restore the heap.
5. Continue until the heap region is size 1.

Heap sort’s strengths are its predictable worst-case time and constant extra space. Its tradeoff is that it is not stable (equal keys may reorder), and in practice it can be slower than well-optimized quicksort variants on many real workloads due to cache behavior and constants.

Priority Queue Applications That Matter

Priority queues are not just a textbook structure. They show up in systems where “best next choice” changes over time.

Scheduling and Resource Management

Operating systems and job schedulers frequently need to pick the next task based on priority, deadlines, or remaining time.

Examples:

• Picking the next runnable process among many
• Handling timed events in simulations (the next event is the smallest timestamp)
• Managing print jobs or batch processing queues

With a priority queue, each insertion of a new job and each selection of the next job stays at $O(\log n)$, which scales well when the queue grows.

Graph Algorithms: Dijkstra’s and Beyond

Heaps are central to shortest-path and spanning-tree algorithms.

• Dijkstra’s algorithm repeatedly extracts the vertex with the smallest tentative distance. A min-heap priority queue makes these extractions efficient.
• Prim’s algorithm for minimum spanning tree similarly benefits from selecting the next lowest-weight edge/vertex candidate.

In these algorithms, the total runtime depends heavily on priority queue performance. Even when the theoretical bound is expressed with $E$ edges and $V$ vertices, the practical speed often hinges on how efficiently you can extract-min and update priorities.

A common operation here is decrease-key (lowering a node’s priority when a better path is found). Classic binary heaps support decrease-key in $O(\log n)$ if you can locate the element’s index. Many implementations handle this by storing a mapping from item to heap index, or by allowing duplicates and ignoring stale entries when popped (a pragmatic approach often used in real-world Dijkstra implementations).

Top-K and Streaming Queries

Need the 100 largest items seen so far, or the 10 smallest latencies in a monitoring window? A heap gives an efficient pattern:

• Maintain a heap of size $k$
• For each new element, compare against the root
• Replace and sift as needed

This keeps memory bounded while offering $O(\log k)$ per update.

Practical Considerations and Common Pitfalls

Choosing Min-Heap vs. Max-Heap

Pick based on what “top priority” means in your problem:

• If you want the earliest time, smallest distance, lowest cost: use a min-heap.
• If you want the largest score, highest urgency, greatest value: use a max-heap.

Many libraries implement only one; converting is often as simple as negating numeric priorities or reversing a comparator.

What Heaps Do Not Provide

A heap is not a general-purpose sorted container:

• Searching for an arbitrary element is $O(n)$.
• Iterating yields elements in heap order, not sorted order.
• Getting the second-best element is not necessarily $O(1)$.

If you need fast search or ordered traversal, balanced trees or sorted arrays may be better fits.

Stability and Tie-Breaking

When priorities are equal, heaps do not preserve insertion order. If you need stable behavior, include a secondary key (such as an incrementing sequence number) so that $(priority,sequence)$ uniquely defines the order.

Why Heaps Remain a Go-To Tool

Binary heaps and priority queues strike a practical balance: fast top access, efficient updates, compact memory layout, and straightforward implementation. With heapify providing linear-time construction and heap sort offering predictable $O(n\log n)$ sorting, heaps are a foundational tool for scheduling systems, event-driven simulations, and graph algorithms where the “next best” choice must be selected repeatedly and quickly.