Step 4 of 7
priority_queue and top-k
std::priority_queue is a heap: push and pop cost O(log n), and top() is always the largest element (by default).
To keep the k largest values of a big stream, use a min-heap of size k: whenever it grows past k, pop the smallest. That's O(n log k) instead of sorting everything.
std::priority_queue<int, std::vector<int>, std::greater<int>> minheap; // top() is the smallest
The three template arguments are: element type, underlying container, comparison.
Your turn: write std::vector<int> top_k(const std::vector<int>& v, int k) returning the k largest values, largest first, using a min-heap of size at most k.