CONCEPT · Candidate Master
Heap / priority queue
also priority queue · binary heap
Insert and extract-min (or max) in O(log n). Dijkstra, Prim, Huffman, and 'always merge the two smallest' are the contest uses.
Intuition
You only ever need the current extreme, not a full sort. Pay log n to keep that extreme honest.
When to reach for it
- Dijkstra / Prim extract-min
- Connect ropes / Huffman
- k screens of Movie Festival II
- Sliding-window median (two heaps)
Usual pits
- C++ priority_queue is a max-heap — Dijkstra needs greater<>
- JS has no std heap; sort-every-time is TLE at 2e5
- Stale Dijkstra entries: skip if popped distance is outdated
- shift() on an array is O(n), not a heap