Priority Queue (Heap) in C++ STL

A priority queue always gives you the most important element first – the largest number, the earliest deadline, the shortest distance. std::priority_queue is implemented as a binary heap: inserting and removing take O(log n), and reading the top is O(1). It powers Dijkstra's algorithm, schedulers and every "top K" interview question.

Max heap: the default

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    for (int x : {30, 10, 50, 20, 40}) pq.push(x);         // O(log n) each
    std::cout << "top " << pq.top() << ", size " << pq.size() << '\n';
    while (!pq.empty()) {
        std::cout << pq.top() << ' ';                       // largest first
        pq.pop();
    }
    std::cout << '\n';
    return 0;
}

top 50, size 5
50 40 30 20 10 

The heap only guarantees the top is the largest; the rest isn't sorted. Push adds at the end and "sifts up"; pop moves the last element to the top and "sifts down" – both O(log n).

Min heap

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq;   // smallest first
    for (int x : {30, 10, 50, 20, 40}) minq.push(x);
    while (!minq.empty()) { std::cout << minq.top() << ' '; minq.pop(); }
    std::cout << '\n';

    std::priority_queue<int> trick;                       // contest trick: push negatives
    for (int x : {30, 10, 50}) trick.push(-x);
    std::cout << "smallest via negation: " << -trick.top() << '\n';
    return 0;
}

10 20 30 40 50 
smallest via negation: 10

Pairs and custom comparators

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

struct Task {
    std::string name;
    int priority;     // higher = more urgent
    int order;        // arrival order, for ties
};

struct LessUrgent {   // returns true if a should come AFTER b
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.order > b.order;           // earlier arrival first on ties
    }
};

int main() {
    using Item = std::pair<int, std::string>;             // (distance, city)
    std::priority_queue<Item, std::vector<Item>, std::greater<Item>> nearest;
    nearest.push({12, "Pune"});
    nearest.push({5, "Lonavala"});
    nearest.push({30, "Nashik"});
    std::cout << "nearest: " << nearest.top().second << " (" << nearest.top().first << " km)\n";

    std::priority_queue<Task, std::vector<Task>, LessUrgent> tasks;
    tasks.push({"reply email", 1, 0});
    tasks.push({"fix outage", 5, 1});
    tasks.push({"review PR", 3, 2});
    tasks.push({"deploy", 5, 3});
    while (!tasks.empty()) { std::cout << tasks.top().name << " | "; tasks.pop(); }
    std::cout << '\n';
    return 0;
}

nearest: Lonavala (5 km)
fix outage | deploy | review PR | reply email | 

Top K elements

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

std::vector<int> top_k(const std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;   // min heap of size k
    for (int x : nums) {
        heap.push(x);
        if (static_cast<int>(heap.size()) > k) heap.pop();               // drop the smallest
    }
    std::vector<int> result;
    while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); }
    return result;                                                       // ascending order
}

int main() {
    std::vector<int> scores{45, 92, 13, 78, 88, 61, 99, 70};
    for (int s : top_k(scores, 3)) std::cout << s << ' ';
    std::cout << '\n';
    return 0;
}

88 92 99 

Keeping a min heap of size k gives O(n log k) – much better than sorting everything (O(n log n)) when k is small, and it works on streams too.

Running median with two heaps

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

int main() {
    std::priority_queue<int> low;                                          // max heap: smaller half
    std::priority_queue<int, std::vector<int>, std::greater<int>> high;    // min heap: larger half
    for (int x : {5, 15, 1, 3, 8, 7}) {
        if (low.empty() || x <= low.top()) low.push(x); else high.push(x);
        if (low.size() > high.size() + 1) { high.push(low.top()); low.pop(); }   // rebalance
        else if (high.size() > low.size()) { low.push(high.top()); high.pop(); }
        double median = low.size() > high.size() ? low.top() : (low.top() + high.top()) / 2.0;
        std::cout << "after " << x << ": median " << median << '\n';
    }
    return 0;
}

after 5: median 5
after 15: median 10
after 1: median 5
after 3: median 4
after 8: median 5
after 7: median 6

Practice

Summary