Heaps and priority queues

A stack is LIFO. A queue is FIFO. A priority queue is neither: it always gives you the element with the highest priority next, regardless of insertion order. The heap is the data structure that makes this efficient.

The min-heap property

A min-heap is a binary tree where every node satisfies one invariant: its value is less than or equal to both of its children. This property holds at every level, all the way from root to leaves.

The consequence is immediate: the minimum element is always at the root. You can read the minimum in O(1) time without searching. You do not need to scan the whole structure.

Push and pop both run in O(log n):

• Push: add the new element at the bottom of the tree (next available position), then "bubble up" — repeatedly swap with the parent if the new element is smaller, until the invariant is restored. The tree has height log₂n, so at most log n swaps.
• Pop (remove minimum): remove the root, move the last leaf to the root position, then "bubble down" — repeatedly swap with the smaller child until the invariant is restored. Again, at most log n swaps.

Compare to a sorted list: inserting into a sorted position is O(n) due to shifting. A heap trades the ability to read any element in O(1) for fast insert/remove-min — the right trade-off when you only ever need the minimum.

Priority queue semantics

A priority queue is the abstract interface; a heap is the typical implementation. The interface is simple:

• push(item) — add an item.
• pop() — remove and return the item with the highest priority.
• peek() — read the highest priority item without removing it (O(1)).

Use cases: job schedulers (always run the highest-priority task), Dijkstra's shortest-path algorithm (always explore the cheapest node next), event simulations (process the earliest event next), A* pathfinding.

The top-K pattern

A common interview and production problem: given n numbers, find the k largest (or smallest). The naive approach sorts everything — O(n log n). But if k is much smaller than n, you can do better.

Algorithm (find k smallest using a max-heap of size k):

1. Build a max-heap containing the first k elements.
2. For each remaining element x in the list:
   • If x is smaller than the heap's maximum (the root), replace the root with x and re-heapify.
3. When done, the heap contains the k smallest elements.

This runs in O(n log k) — you only maintain k elements in the heap, so each heapify is O(log k) not O(log n). When k is small (say, k=10 and n=1 million), this is dramatically faster than sorting all n elements.

Python's heapq module

Python implements a min-heap on a plain list. The module is heapq:

import heapq

nums = [5, 1, 8, 3, 2]
heapq.heapify(nums)       # rearranges in-place into heap order — O(n)
print(nums[0])            # 1 — minimum is always at index 0

heapq.heappush(nums, 0)   # push 0 — O(log n)
print(heapq.heappop(nums))# 0 — pops minimum — O(log n)

There is no heappopmax — heapq is a min-heap only. To simulate a max-heap, negate all values: push -x and negate the result when you pop.

Where to go next

Next: heaps in practice — using heapq to implement find_k_smallest and a priority queue for tasks, both running in the browser.