The idea
A heap, priority_queue in C++, gives the best item in O(1) and inserts or removes it in O(log n). Use it when you repeatedly need the current best while items keep arriving: k-th smallest, merging, greedy scheduling, Dijkstra.
priority_queue<int> is a max-heap. For a min-heap write priority_queue<int, vector<int>, greater<int>>.
A heap cannot delete an arbitrary item. The usual fix is lazy deletion: remember deleted values in a second heap and drop them only when they reach the top.
Sample problem
1046. Last Stone Weight ↗ Easy
Repeatedly smash the two heaviest stones together. If they are equal both are destroyed; otherwise the lighter is destroyed and the heavier loses that weight. Return the weight of the last stone, or 0.
stones = [2,7,4,1,8,1] output = 1
Why the solution works
Each round needs the two heaviest stones of a collection that keeps changing: stones are removed and a new one may be added.
Sorting after every round would cost O(n log n) each time. A max-heap gives the heaviest stone in O(1) and removes or inserts in O(log n), which is exactly the pattern “take the best, put something back”.
Complexity: O(n log n) time: at most n rounds, each with a few heap operations. O(n) memory.
Watch out
- The default
priority_queueis a max-heap; forgettinggreater<>silently gives the largest item. - There is no erase or decrease-key: push a new entry and skip stale ones when they surface.
- With pairs, comparison is by
first, thensecond: put the priority first.