Heaps and Priority Queues
Retrieval: when is it a heap?
Two problems rebuilt cold, plus the signal that separates a heap from a sort.
Key idea
Three signals
You need the best item repeatedly while the collection keeps changing. Sorting once does not survive insertions; a heap does.
You need only k of them and k is much smaller than n. A bounded heap is O(n log k) and O(k) space where sorting is O(n log n) and O(n).
The data arrives as a stream with no end. Sorting is not available at all, and any answer has to be maintained rather than computed.
Tip
And when not to
If you need everything in order, just sort. Popping a whole heap is heapsort with worse constants and more code.
If you need the middle rather than an extreme, one heap cannot do it and you want two. If you need to remove arbitrary items, a heap cannot, and lazy deletion is the usual workaround.
Heap or sort?
You have ten million log entries on disk and need the fifty with the highest severity. Memory is limited. What fits best?
Top K Frequent Elements, with a heap this time
You solved this in Unit 1 with counting buckets. Build it again with a bounded heap and compare the two costs out loud before you start.
Serialize and Deserialize Binary Tree, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.