Chapter 34

Home

Priority Queues and Heaps

A queue serves elements in FIFO order. A priority queue serves elements by priority — the largest (or smallest) element always comes out first, regardless of insertion order. Under the hood: a heap.

What Makes a Priority Queue Special

In a regular queue, insertion order determines service order. In a priority queue, the element with the highest priority is always at the front — even if it was inserted last.

Insert: 3 → 7 → 1 → 9 → 4 Pop: 9 7 4 3 1 (max-heap: largest first) Priority queue = max-heap by default in most languages

C++ — std::priority_queue

#include <bits/stdc++.h>
using namespace std;

int main() {
    // max-heap (default): largest element on top
    priority_queue<int> pq;

    pq.push(10);
    pq.push(40);
    pq.push(20);
    pq.push(5);

    cout << pq.top() << "\n";  // 40 (largest)
    pq.pop();                     // remove 40
    cout << pq.top() << "\n";  // 20
    cout << pq.size() << "\n";  // 3
    cout << pq.empty() << "\n"; // 0

    return 0;
}

Rust — BinaryHeap

use std::collections::BinaryHeap;

fn main() {
    // max-heap: largest element on top
    let mut pq = BinaryHeap::new();

    pq.push(10);
    pq.push(40);
    pq.push(20);
    pq.push(5);

    println!("{}", pq.peek().unwrap());  // 40
    pq.pop();                              // remove 40
    println!("{}", pq.peek().unwrap());  // 20
    println!("{}", pq.len());            // 3
    println!("{}", pq.is_empty());       // false
}

Min-Heap: Getting the Smallest Element

By default, priority queues are max-heaps (largest first). To get smallest-first, you need a min-heap.

C++ — min-heap

// Store negatives, or use greater:
priority_queue<int, vector<int>, greater<int>> min_pq;

// Or push negative values:
priority_queue<int> min_pq;
min_pq.push(-5);   // actually -5 → top = -5 (smallest magnitude)
min_pq.push(-3);
int val = -min_pq.top();  // 3

Rust — min-heap via std::cmp::Reverse

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut min_pq: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_pq.push(Reverse(10));
min_pq.push(Reverse(3));
min_pq.push(Reverse(7));

println!("{}", min_pq.peek().unwrap().0);  // 3 (smallest)

Reverse wraps a value and reverses its ordering. The heap still behaves as a max-heap on the wrapper, but the wrapper's max is the smallest original value.

💡 The negative-value trick (C++)

Storing negative values is a common contest hack. Push -x instead of x, and the max-heap effectively becomes a min-heap. Negate again on pop. It avoids the verbose greater<int> syntax.

Real Use: Top K Elements

Find the K largest elements in an array. Naive: sort and take the last K (O(N log N)). With a min-heap of size K: O(N log K).

C++ — top K with min-heap

vector<int> top_k(vector<int>& arr, int k) {
    priority_queue<int, vector<int>, greater<int>> min_pq;

    for (int x : arr) {
        min_pq.push(x);
        if (min_pq.size() > k) min_pq.pop();  // evict smallest
    }

    vector<int> result;
    while (!min_pq.empty()) {
        result.push_back(min_pq.top());
        min_pq.pop();
    }
    return result;
}

📐 How the K-heap trick works

Keep a min-heap of size K. For each new element, push it. If the heap exceeds K, pop the smallest — it's guaranteed not to be in the top K. When you're done, the heap contains exactly the K largest elements. O(N log K) instead of O(N log N).

Key Takeaways

Practice