Top-k Problems and Merging

The k biggest, without sorting everything

Keep a min-heap of size k. If a new item beats the smallest of your top k (the heap's top), swap it in:

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    vector<int> scores = {5, 12, 3, 41, 7, 19, 2, 33};
    int k = 3;
    priority_queue<int, vector<int>, greater<int>> top;
    for (int s : scores) {
        top.push(s);
        if ((int)top.size() > k) top.pop();      // throw out the smallest
    }
    vector<int> best;
    while (!top.empty()) { best.push_back(top.top()); top.pop(); }
    for (int i = (int)best.size() - 1; i >= 0; i--) cout << best[i] << ' ';
    cout << endl;
    return 0;
}

Output

41 33 19 

O(n log k) – much faster than sorting when k is small.

Think of it like this: A judge who only keeps the current top 3 photos on the desk and compares each new photo with the worst of them.

Merging sorted lists

#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> lists = {{1, 4, 9}, {2, 3, 10}, {5, 6}};
    // (value, which list, position)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (int i = 0; i < (int)lists.size(); i++) pq.push({lists[i][0], i, 0});
    while (!pq.empty()) {
        auto [value, which, pos] = pq.top();
        pq.pop();
        cout << value << ' ';
        if (pos + 1 < (int)lists[which].size()) pq.push({lists[which][pos + 1], which, pos + 1});
    }
    cout << endl;
    return 0;
}

Output

1 2 3 4 5 6 9 10 

Remember: Need the smallest/biggest item over and over while things change? Use a heap.