Card 08/ 08
Recap: Heap Patterns
The top is the item to throw away: a min-heap of k for the largest, a heap of fronts for k lists, two heaps for a middle.
A heap pattern holds only the items still in contention, and the heap's top is always the next item to act on: the one to throw away for a top-k question, the next to output for a merge, or the middle for a running median. Choosing the heap means naming that item first:
| Question | Heap | Size | Cost | Alternative |
|---|---|---|---|---|
| k largest | Min-heap | k | O(n log k) | Sort when asked once and n is small |
| k smallest or k closest | Max-heap | k | O(n log k) | Quickselect for one rank in memory |
| Merge k sorted lists | Min-heap of fronts | k | O(n log k) | Sort everything, O(n log n) |
| Running median | Max-heap and min-heap | n split in two | O(log n) an arrival | Sort again each time, O(n²) in all |
Python's heapq is a min-heap, so a max-heap pushes negated keys; Java's PriorityQueue takes a Comparator; TypeScript needs a small heap of its own. Capping the wrong kind of heap keeps the wrong k, with no error, and only the top of a heap is in a known place, so its contents are sorted before they are shown.
← → move through sections and cards