C++ priority_queue and the top-k pattern
std::priority_queue is a binary heap adaptor. By default it is a max-heap: top returns the largest element. push and pop take O(log n) and top takes O(1). To get a min-heap, give it std::greater<int> as the comparison and std::vector<int> as the underlying container.
C++
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> max_heap;
for (int v : {5, 1, 8, 3, 9, 2}) {
max_heap.push(v);
}
std::cout << "largest first:";
while (!max_heap.empty()) {
std::cout << " " << max_heap.top();
max_heap.pop();
}
std::cout << "\n";
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
for (int v : {5, 1, 8, 3}) {
min_heap.push(v);
}
std::cout << "smallest: " << min_heap.top() << "\n";
const std::size_t k = 3;
std::priority_queue<int, std::vector<int>, std::greater<int>> top;
for (int v : {7, 12, 3, 19, 5, 11, 2, 15}) {
top.push(v);
if (top.size() > k) {
top.pop();
}
}
std::vector<int> result;
while (!top.empty()) {
result.push_back(top.top());
top.pop();
}
std::cout << "top 3 ascending:";
for (int v : result) std::cout << " " << v;
std::cout << "\n";
}