Binary heaps and priority queues

Complete binary tree in an array: every parent beats its children. Always grab the extreme — the priority queue.

Weak order, one strong guarantee

• Parent ≤ children (min-heap) — nothing about siblings
• Min is always the root → peek O(1)
• Children of i at 2i+1, 2i+2 — no pointers (array-as-tree)
• push: sift up · pop: sift down — O(log n)

Watch push (up) and pop (down)

Push 1 → sifts up to the root. Pop → last leaf to root, sifts down. Never fully sorted — just parent < children.

Costs

peek O(1) · push/pop O(log n) · build O(n). heapq ≈13× faster (C).

Only the extreme is fast

• Finding/removing an arbitrary value: O(n)
• heapq is a MIN-heap — negate for max; push (priority, item) tuples
• No decrease-key → lazy deletion (Dijkstra's trick)

Takeaway

Minimum effort to answer one question: what's the extreme? The engine of Dijkstra, Prim, Huffman, schedulers. Next: tries.