Heaps and Priority Queues

A heap keeps the smallest (or largest) item instantly available, with O(log n) insert and remove, without keeping everything sorted.

What it is

• A complete binary tree: every level full except possibly the last, which fills left to right with no gaps. Keeps height about log n.
• Heap property, min-heap: parent <= each child at every node, so the minimum sits at the root. Max-heap flips it (parent >= each child).
• Partially ordered only: the root is the extreme value; the rest is not sorted.

Array layout

Nodes numbered level by level, left to right, from 0. For index i:

• left child: 2*i + 1
• right child: 2*i + 2
• parent: (i - 1) // 2

No node objects or pointers; just index math on a flat list.

Operations

• Push: append at the end, then sift-up (swap with parent while smaller). Climbs at most the height.
• Pop: take root, move last element to root, shrink by one, then sift-down (swap with the smaller child while larger). Swapping with the smaller child preserves the property.
• Heapify: sift-down on every internal node from index (n // 2) - 1 down to 0. Builds in O(n), beating n pushes at O(n log n).

Cost

Python heapq

• Min-heap on a plain list: heappush, heappop (O(log n)), heapify (O(n)), heap[0] peek (O(1)).
• It is a normal list; only mutate it through heapq functions.
• No max-heap: store negatives (min-heap over negatives acts as max-heap), negate again on the way out.
• Priority queue: push tuples (priority, item); smallest priority pops first. Add a unique counter (priority, counter, item) so ties never compare the items.
• Powers Dijkstra, A*, Huffman coding, event-driven simulations.

Gotchas

• A heap is not sorted; only the root is guaranteed extreme.
• Mutating the list behind heapq’s back breaks the invariant.
• In hand-written sift-down, guard 2*i+1 < n and 2*i+2 < n before reading a child.
• Tuple ties fall through to the next element; non-comparable items raise TypeError.