Heaps and Priority Queues: A Practical Guide

What makes a heap useful?

A binary min-heap is a complete binary tree where every parent is no greater than its children. The root therefore holds the minimum item. The complete-tree shape can be stored compactly in an array: for zero-based index i, its children are 2i + 1 and 2i + 2. A max-heap reverses the comparison.

A heap does not keep all items sorted. It guarantees only the relationship needed to access the current extreme quickly. This makes it a better choice than sorting when values arrive over time or when only a few best candidates are needed.

Operation costs

• Peek at the minimum/maximum: O(1).
• Insert an item: O(log n) by bubbling it up.
• Remove the root: O(log n) by moving the final item to the root and sifting it down.
• Build a heap from an array: O(n) with bottom-up heapify.

In Python, heapq provides a min-heap:

import heapq

numbers = [8, 3, 5, 1]
heapq.heapify(numbers)       # in-place, O(n)
heapq.heappush(numbers, 2)   # O(log n)
smallest = heapq.heappop(numbers)  # 1, O(log n)

To maintain the largest k values in a stream, keep a min-heap of size at most k. The smallest retained value sits at the root and can be discarded whenever a better value arrives. This takes O(n log k) time and O(k) space.

When to reach for a priority queue

• Top K: keep a bounded heap when k is much smaller than the input.
• Merge sorted sequences: repeatedly select the next smallest head among the sequences.
• Scheduling: process the event with the earliest deadline or highest priority.
• Shortest paths: Dijkstra uses a min-heap to visit the unsettled vertex with the smallest tentative distance.

If the task needs arbitrary deletion or fast lookup of an existing key, a binary heap alone may not be enough. Also avoid mutating a priority key in place unless the heap is repaired; many standard libraries do not track such changes automatically.