DSA Notes

Data Structures

Heap

Always hands you the smallest (or largest) item.

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_queue is a max-heap; forgetting greater<> 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, then second: put the priority first.
Watch it run

Try your own input

Practise on LeetCode