Step 4 of 7

priority_queue and top-k

std::priority_queue (from <queue>) is a heap: a structure that always knows its largest element. push and pop cost O(log n), and top() is always the maximum.

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> maxheap;
    for (int x : {5, 1, 8, 3, 9, 2}) maxheap.push(x);
    std::cout << "max-heap pops: ";
    while (!maxheap.empty()) {
        std::cout << maxheap.top() << " ";
        maxheap.pop();
    }

    std::priority_queue<int, std::vector<int>, std::greater<int>> minheap;
    for (int x : {5, 1, 8, 3, 9, 2}) minheap.push(x);
    std::cout << "\nmin-heap top: " << minheap.top() << "\n";
}

max-heap pops: 9 8 5 3 2 1 
min-heap top: 1

The three template arguments of the min-heap are: element type, underlying container, comparison. std::greater<int> flips the order, so top() becomes the smallest.

Top k with a min-heap

To keep the k largest values from a big list, keep a min-heap that never holds more than k values:

1. Push each value.
2. If the heap now has more than k values, pop. The popped value is the smallest in the heap, so it can't be among the k largest.

At the end, the heap holds the k largest values. Each step is O(log k), so the total is O(n log k), which beats sorting everything (O(n log n)) when k is small.

The heap pops smallest first, so to return the values largest first, pop them all into a vector and then reverse it (or fill the vector from the back).

Common mistakes

• Using the default max-heap for top k. It pops the largest, which is the one you wanted to keep.
• Calling top() or pop() on an empty heap. Handle k == 0 and short inputs.

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.

Previous: deque, the double-ended queue Next: Iterators