Heaps and Priority Queues
Keep a changing collection ready to hand you its smallest or largest item in O(log n), and use that for top-k and merging problems.
The problem
Many tasks need the same move again and again: look at the smallest (or largest) item, remove it, and let new items arrive in between.
- A scheduler always runs the most urgent job, while new jobs keep coming in.
- A stream of numbers, and after each one you must report the 3rd largest so far.
- Merge 100 sorted files into one sorted file.
A priority queue is the abstract structure for this: push(x), top() (peek the best item) and pop() (remove it). A heap is the usual way to build one.
1 of 9