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 task

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.

Challenge 2

Each task is a {priority, name} pair. Write std::vector<std::string> run_order(const std::vector<std::pair<int, std::string>>& tasks) that returns the names in the order they run: highest priority first, and equal priorities in alphabetical order. Use a std::priority_queue with your own comparison, not sorting.

Challenge 3

Write int last_stone(const std::vector<int>& stones). Each turn, smash the two heaviest stones together: if they weigh the same both are destroyed, otherwise the lighter is destroyed and the heavier loses that much weight and goes back. Return the weight of the stone that is left, or 0 if none is. Use a std::priority_queue.

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