Min-Heap via std::priority_queue
`std::priority_queue` is a max-heap by default. To get a min-heap you flip the comparator. This snippet shows the three common forms: a min-heap of ints with `std::greater`, a min-heap of pairs sorting by first element, and a custom comparator over a struct for things like Dijkstra. All run in O(log n) per push/pop.
1,192 views
35
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
int main() {
// Default: max-heap. priority_queue<T> == priority_queue<T, vector<T>, less<T>>.
std::priority_queue<int> mx;
for (int x : {5, 1, 4, 2, 3}) mx.push(x);
std::cout << "max top=" << mx.top() << "\n"; // 5
// Min-heap: pass std::greater as the comparator.
std::priority_queue<int, std::vector<int>, std::greater<int>> mn;
for (int x : {5, 1, 4, 2, 3}) mn.push(x);
std::cout << "min top=" << mn.top() << "\n"; // 1
// Drain in priority order.
while (!mn.empty()) {
std::cout << mn.top() << " ";
mn.pop();
}
std::cout << "\n";
return 0;
}std::priority_queue is a heap-backed adapter over a sequence container, with top returning the highest-priority element. The third template parameter is the comparator: less<T> (the default) gives a max-heap because the standard's heap routines pop the element for which the comparator returns true MOST often (the largest). Swap to greater<T> for a min-heap. Both push and pop are O(log n); top is O(1).
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <utility>
#include <functional>
void demoPairs() {
// Pairs already compare lexicographically (first, then second), so a
// min-heap of pair<int, string> orders by smallest int first.
using P = std::pair<int, std::string>;
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
pq.push({3, "banana"});
pq.push({1, "apple"});
pq.push({2, "cherry"});
while (!pq.empty()) {
const auto& top = pq.top();
std::cout << top.first << " -> " << top.second << "\n";
pq.pop();
}
}
int main() {
demoPairs();
return 0;
}std::pair already has a built-in lexicographic operator< and operator>, so a min-heap of pairs naturally sorts by the first element and uses the second only as a tie-breaker. This is the workhorse pattern for Dijkstra (pair<distance, node>), event timelines (pair<timestamp, payload>), and any priority-with-payload structure. If you need to sort by the second element instead, swap the order in the pair or write a custom comparator (next accordion). Avoid pair<float, ...> keys when ties matter, since float equality is fragile.
#include <iostream>
#include <queue>
#include <vector>
#include <string>
struct Job {
int priority;
std::string name;
};
struct JobLess {
// Min-heap means "the SMALLEST priority comes out first", so the
// comparator returns true when 'a' has greater priority than 'b'.
bool operator()(const Job& a, const Job& b) const {
return a.priority > b.priority;
}
};
void demoCustom() {
std::priority_queue<Job, std::vector<Job>, JobLess> pq;
pq.push({3, "build"});
pq.push({1, "deploy"});
pq.push({2, "test"});
while (!pq.empty()) {
const Job& j = pq.top();
std::cout << j.priority << ": " << j.name << "\n";
pq.pop();
}
}
int main() {
demoCustom();
return 0;
}Define a comparator as a struct with operator() returning bool, then pass the type as the third template parameter. The semantics inverts what you might expect: returning true means "the first argument is LOWER priority than the second", so for a min-heap on priority, you compare a.priority > b.priority. A common bug is to copy the comparator from a sort and end up with a max-heap by accident; always trace through with two known elements before trusting the result. Lambdas can also serve as comparators but require declaring the type with decltype plus passing the lambda to the constructor, which is uglier than a small struct.