Heaps and priority queues

A binary search tree keeps everything ordered. Often you do not need that — you only need to know the smallest element, then remove it and know the next smallest. A heap provides exactly that weaker guarantee for a fraction of the bookkeeping, and it needs no pointers at all: it fits in a flat array.

Insert values and extract the minimum below. Each operation really sifts through the array; the tree drawn is just the same array read by index.

The array is the tree #

A heap is a complete binary tree — every level full except possibly the last, filled left to right — which lets it be stored contiguously with no pointers:

• index $i$ has children at $2i+1$ and $2i+2$;
• index $i$ has its parent at $\lfloor (i-1)/2 \rfloor$.

Complete means the array has no gaps, so the height is always $\lfloor \log_2 n \rfloor$ — the tree is balanced by construction. That is what a heap gives up the BST's fully sorted order to gain.

Sift up and sift down #

Two procedures maintain the property:

• Sift up after appending: while the new element is smaller than its parent, swap them. At most one path up, so $O(\log n)$.
• Sift down after removing the root: move the last leaf to the root, then repeatedly swap it with the smaller child until both children are larger. Again $O(\log n)$.

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
smallest = heapq.heappop(heap)   # 2

The array heap is the heap; heapq provides the operations. There is no separate class.

Priority queues #

The usual reason to reach for a heap is a priority queue: a queue that removes the item with the highest priority rather than the oldest. Because both operations are $O(\log n)$, scheduling many tasks costs $O(n \log n)$ overall instead of the $O(n^2)$ a repeatedly re-sorted list would cost. Dijkstra's shortest-path algorithm and event simulation both run on this structure.

Where next: hash tables — O(1) lookup without maintaining any order at all.