Priority Queue and Heaps

A priority queue is the right tool when one item matters more than all the others and that item keeps changing. It gives you the current maximum or minimum in $O(\log n)$, which is why it shows up in Dijkstra, greedy scheduling, k-way merge, and any problem that says "process the best available item next."

Difficulty: Beginner | Prerequisites: Set and Multiset

---

Intuition

You have a task queue with urgencies: [5, 3, 8, 1, 9, 2]. Always process the most urgent task first—lower number means higher urgency—and new work can arrive at any time.

Operations to perform:

1. Extract-min from [5, 3, 8, 1, 9, 2]
2. Insert 4
3. Extract-min
4. Insert 0
5. Extract-min

Naive approach—unsorted array. Insertion is $O(1)$ (just append). But each extract-min must scan the entire array to find the minimum:

  Op 1: Extract-min from [5, 3, 8, 1, 9, 2]
        Scan all 6 elements -> min is 1 (index 3)       5 comparisons
        Swap with last, shrink -> [5, 3, 8, 2, 9]

  Op 2: Insert 4
        Append -> [5, 3, 8, 2, 9, 4]                    0 comparisons

  Op 3: Extract-min from [5, 3, 8, 2, 9, 4]
        Scan all 6 elements -> min is 2 (index 3)       5 comparisons
        Swap with last, shrink -> [5, 3, 8, 4, 9]

  Op 4: Insert 0
        Append -> [5, 3, 8, 4, 9, 0]                    0 comparisons

  Op 5: Extract-min from [5, 3, 8, 4, 9, 0]
        Scan all 6 elements -> min is 0 (index 5)       5 comparisons
        Swap with last, shrink -> [5, 3, 8, 4, 9]

  Total: 15 comparisons for 3 extract-mins.
  Each extract-min is O(n).

What about keeping a sorted array? Then extract-min becomes $O(1)$, but every insertion turns into an $O(n)$ shift. The bottleneck moves, but it does not disappear.

Either way, with $n={10}^5$ elements and $m={10}^5$ operations, you're doing $O(nm)={10}^{10}$ work—orders of magnitude over a 2-second time limit.

We're paying linear time for the same decision over and over. There has to be a better way.

If you arrange the elements in a binary tree where every parent is smaller than or equal to its children, the minimum always sits at the root. Insertions and removals only disturb one root-to-leaf path, so the repair work stays at $O(\log n)$ instead of $O(n)$.

Store that tree level-by-level in a flat array. Node $i$'s children live at $2i+1$ and $2i+2$; its parent sits at $\lfloor (i-1)/2\rfloor$. That gives you the tree structure without pointers or allocations—just index arithmetic and good cache locality.

Analogy—inverted tournament bracket. Picture a tournament where the weakest player always wins and keeps moving up. The smaller value advances in every round, so the overall minimum ends up at the top. When you remove that champion, you only replay matches along one path from root to leaf to fill the gap—not the whole tournament.

Where the analogy breaks: In a real tournament, each match is between siblings that already competed directly. In a heap, sift-down compares a node against both children and swaps with the smaller one, so the siblings never face each other. Insertion (sift-up) also has no tournament equivalent; it is closer to a new player challenging successive parents on the way to the root.

Same problem as above, now with a min-heap.

Step 0: Build min-heap from [5, 3, 8, 1, 9, 2]

Insert elements one by one; each new element sifts up to restore the heap property. After all 6 insertions:

  Tree view:                Array view:

         1                  +---+---+---+---+---+---+
        / \                 | 1 | 3 | 2 | 5 | 9 | 8 |
       3   2                +---+---+---+---+---+---+
      / \ /                  [0] [1] [2] [3] [4] [5]
     5  9 8
                            parent(k)   = (k-1) / 2
                            children(k) = 2k+1, 2k+2

  Check: 1<=3, 1<=2, 3<=5, 3<=9, 2<=8.
  Every parent <= its children. Heap property holds.

Step 1: Extract-min—removes 1

Swap root (1) with last element (8). Remove last. Sift 8 down.

  After swap + remove:        Sift down 8:
                              children are 3 (idx 1), 2 (idx 2)
         8                    min child = 2. Since 8 > 2, swap.
        / \
       3   2       -->              2
      / \                          / \
     5   9                        3   8
                                 / \
  Array: [8,3,2,5,9]           5   9

                              Array: [2,3,8,5,9]
                              8 at [2] has no children. Done.
                              Cost: 2 comparisons.

Step 2: Insert 4

Append 4 at index [5]. Sift up: parent at [2] is 8. Since $4<8$, swap. New parent at [0] is 2. Since $4>2$, stop.

  Append 4:                   After sift-up:

         2                           2
        / \                         / \
       3   8         -->           3   4
      / \ /                       / \ /
     5  9 4                      5  9 8

  Array: [2,3,8,5,9,4]        Array: [2,3,4,5,9,8]
  Cost: 2 comparisons (1 swap, 1 stop).

Step 3: Extract-min—removes 2

Swap root (2) with last (8). Remove last. Sift 8 down two levels.

  After swap + remove:    Sift level 1:          Sift level 2:
                          min child = 3           min child = 5
         8                       3                       3
        / \                     / \                     / \
       3   4     -->           8   4       -->         5   4
      / \                     / \                     / \
     5   9                   5   9                   8   9

  [8,3,4,5,9]            [3,8,4,5,9]             [3,5,4,8,9]
  Cost: 4 comparisons (2 levels, 2 comparisons each).

Step 4: Insert 0

Append 0 at [5]. Sift up: parent at [2] is 4. Since $0<4$, swap. Parent at [0] is 3. Since $0<3$, swap. Now at root.

  Append 0:               Sift to [2]:           Sift to root:

         3                       3                       0
        / \                     / \                     / \
       5   4     -->           5   0       -->         5   3
      / \ /                   / \ /                   / \ /
     8  9 0                  8  9 4                  8  9 4

  [3,5,4,8,9,0]          [3,5,0,8,9,4]           [0,5,3,8,9,4]
  Cost: 2 comparisons (2 swaps).

Step 5: Extract-min—removes 0

Swap root (0) with last (4). Remove last. Sift 4 down.

  After swap + remove:     Sift down:
                           min child = 3
         4                        3
        / \                      / \
       5   3       -->          5   4
      / \                      / \
     8   9                    8   9

  [4,5,3,8,9]              [3,5,4,8,9]
  Cost: 2 comparisons.

Operation count comparison:

	Naive (unsorted array)	Min-heap
3 extract-mins	5 + 5 + 5 = 15 comparisons	2 + 4 + 2 = 8 comparisons
2 inserts	0 (append only)	2 + 2 = 4 comparisons
Total	15	12

For 6 elements the gap is modest. But each heap operation is $O(\log n)$ vs $O(n)$. At $n={10}^5$: a heap extract-min touches $\sim 17$ nodes per call; naive scans all $\sim \mathrm{100,000}$. After $m={10}^5$ operations: $\sim 1.7\times {10}^6$ vs ${10}^{10}$—the difference between 10 ms and TLE.

The Min-Heap Property and Why It Costs Only $\log n$

+--------------------------------------------------------------+
| INVARIANT (Min-Heap Property):                               |
|                                                              |
| For every node i (except the root):                          |
|     arr[parent(i)] <= arr[i]                                 |
|                                                              |
| Equivalently: every parent <= both its children.             |
| The minimum element is ALWAYS at the root (index 0).         |
+--------------------------------------------------------------+

Two operations maintain this invariant:

• Sift-up (after insert): a freshly appended element at the bottom may be smaller than its parent. Swap it upward repeatedly until the parent wins or it reaches the root. Step 4 above shows the extreme case—0 bubbled all the way to the root because it beat every ancestor on the path.

• Sift-down (after extract-min): the replacement element placed at the root may be larger than its children. Swap it with its smaller child and repeat downward. Step 3 shows 8 sinking two levels because both 3 and 5 were smaller.

Why $O(\log n)$? A complete binary tree with $n$ nodes has height $\lfloor {\log }_{2}n\rfloor$. Both sift-up and sift-down follow at most one root-to-leaf path, so neither operation touches more than $\lfloor {\log }_{2}n\rfloor +1$ nodes.

Build in $O(n)$, not $O(n\log n)$: When all $n$ elements are available upfront, call sift-down from the bottom up (Floyd's algorithm) rather than inserting one by one. Most nodes sit near the leaves and sift down only a few levels, so the work is front-loaded where it is cheapest. Specifically, the number of nodes at height $h$ is at most $\lceil n/2^{h+1}\rceil$, each sifting down $O(h)$ levels, and the sum telescopes:

$$\sum _{h=0}^{\lfloor \log n\rfloor }\lceil \frac{n}{2^{h+1}}\rceil \cdot h\le 2n=O(n)$$

Priority = "What Goes First?"

The same structure appears everywhere greedy algorithms meet dynamic data: pick the best available option, do some work, and repeat. The priority changes, but the question is always the same—what goes first?

    Priority = "what goes first?"

    Dijkstra:         priority = current distance    (smallest)
    Prim's MST:       priority = cheapest edge       (smallest)
    Task scheduling:  priority = deadline            (earliest)
    Huffman coding:   priority = frequency           (smallest)
    K-way merge:      priority = head element        (smallest)

    +--------+       +--------+       +--------+
    | Insert |------>|  HEAP  |------>| Extract|
    | O(lgn) |       | (black |       | O(lgn) |
    +--------+       |  box)  |       +--------+
                     +--------+
    You only ever see the TOP -- everything else is hidden.

Lazy deletion is a general technique, not a Dijkstra-specific hack. Any time elements become invalidated—because their priority changed or they are no longer relevant—push the new version and skip stale entries on pop. That pattern applies to Dijkstra, Prim, event simulation, and more.

The array-to-tree mapping is the key to understanding heaps. The STL heap stores a complete binary tree in a flat array:

    Array: [2, 3, 4, 7, 5, 6, 9]   (min-heap)
    
    Tree view:
              2            index 0
            /   \
           3     4         index 1, 2
          / \   / \
         7   5 6   9       index 3, 4, 5, 6
    
    parent(i) = (i-1)/2
    left(i)   = 2*i + 1
    right(i)  = 2*i + 2
    
    Height = floor(log2(n)) --> all ops are O(log n)

With that index arithmetic internalized, the heap stops feeling like a black box and becomes a flat array with structural guarantees.

When to Reach for This

Trigger phrases—if you see these in a problem, think heap:

• "Repeatedly find/remove the minimum (or maximum)"—the core heap use case.
• "Process elements in order of priority / cost / deadline"—greedy + heap.
• "Shortest path" or "Dijkstra"—min-heap of (distance, node) pairs.
• "Merge $k$ sorted lists or streams"—min-heap holding $k$ heads.
• "Maintain the $k$-th largest (or smallest) element"—fixed-size heap of size $k$.

Counter-examples—looks like heap territory, but isn't:

• "Find AND remove arbitrary elements, not just the min/max." A heap only exposes the top element. You need std::set or std::multiset for arbitrary removal. See: Set and Multiset.
• "Check whether a specific value exists in the collection." Heaps don't support lookup—searching is $O(n)$. Use a hash set or balanced BST instead.
• "Track the running median." A single heap doesn't help—you need the two-heap trick (lower-half max-heap + upper-half min-heap). This is covered in the Two-Heap Median Maintenance pattern below.
• "Need both min and max simultaneously." A single heap only exposes one extreme. Use two heaps with lazy deletion, or switch to std::multiset (*s.begin() and *s.rbegin()).

See also: Dijkstra's Algorithm (primary graph application), Segment Tree (range-query alternative), Data Structure Selection Guide.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
priority_queue<T>	<queue>	Max-heap. top() returns largest element.	--
priority_queue<T, vector<T>, greater<T>>	<queue>	Min-heap. top() returns smallest element.	--
pq.push(x)	<queue>	Insert element $x$.	$O(\log n)$
pq.top()	<queue>	Access the top (max or min) element. Does not remove.	$O(1)$
pq.pop()	<queue>	Remove the top element.	$O(\log n)$
pq.size()	<queue>	Number of elements.	$O(1)$
pq.empty()	<queue>	Whether the queue is empty.	$O(1)$
pq.emplace(args...)	<queue>	Construct element in-place.	$O(\log n)$
make_heap(first, last)	<algorithm>	Turn a range into a max-heap in-place.	$O(n)$
push_heap(first, last)	<algorithm>	Sift up the element at last-1 (call after appending).	$O(\log n)$
pop_heap(first, last)	<algorithm>	Move top to last-1 and re-heapify (call pop_back after).	$O(\log n)$
sort_heap(first, last)	<algorithm>	Sort a heap range in ascending order.	$O(n\log n)$
is_heap(first, last)	<algorithm>	Check if range satisfies heap property.	$O(n)$

Min-heap shorthand (the declaration everyone forgets):

priority_queue<int, vector<int>, greater<int>> min_pq;

With pairs—sorts by first element, then second (both max by default):

priority_queue<pair<int,int>> pq;
pq.push({cost, node}); // largest cost on top

// For min-cost on top:
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
// Or just negate the values:
pq.push({-cost, node}); // smallest cost on top (via negation trick)

---

Implementation

Minimal Contest Templates

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

// --- Dijkstra with min-heap (negation trick) ---
// Graph: adjacency list with (neighbor, weight)
vector<long long> dijkstra(int src, const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    priority_queue<pair<long long,int>> pq; // max-heap, negate distances
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        if (d > dist[u]) continue; // stale entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist;
}

// --- Running median with two heaps ---
struct MedianTracker {
    priority_queue<int> lo;                                    // max-heap: lower half
    priority_queue<int, vector<int>, greater<int>> hi;         // min-heap: upper half

    void add(int x) {
        lo.push(x);
        hi.push(lo.top()); lo.pop();
        if (hi.size() > lo.size()) { lo.push(hi.top()); hi.pop(); }
    }
    double median() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

int main() {
    // Example: Dijkstra
    int n = 5, m = 6;
    vector<vector<pair<int,int>>> adj(n);
    // ... read edges ...
    auto dist = dijkstra(0, adj);

    // Example: Running median
    MedianTracker mt;
    for (int x : {5, 2, 8, 1, 9}) {
        mt.add(x);
        cout << mt.median() << "\n";
    }
}

Annotated Version

The same code with every non-obvious decision explained inline:

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

// Dijkstra's shortest path using a priority_queue.
//
// Why negation trick?
//   C++ priority_queue is a max-heap. We want the smallest distance on top.
//   Instead of typing the verbose greater<> declaration, we just negate
//   distances: push(-dist), and the max-heap gives us the most-negative
//   value first, which is the smallest real distance.
//
// Why "if (d > dist[u]) continue"?
//   We can't decrease-key in a priority_queue. Instead, we push duplicate
//   entries and skip stale ones. This is "lazy deletion." The total number
//   of pushes is O(m), so the complexity is O(m log m) = O(m log n) for
//   simple graphs.
//
vector<long long> dijkstra(int src, const vector<vector<pair<int,int>>>& adj) {
    int n = (int)adj.size();
    vector<long long> dist(n, LLONG_MAX);  // dist[v] = shortest distance from src to v
    // Max-heap of (-distance, node). Most-negative = smallest distance.
    priority_queue<pair<long long, int>> pq;

    dist[src] = 0;
    pq.push({0, src});  // distance 0 to source; negated 0 is still 0

    while (!pq.empty()) {
        auto [neg_d, u] = pq.top();
        pq.pop();
        long long d = -neg_d;  // recover the real distance

        // If we already found a shorter path to u, skip this stale entry.
        // This is the key to lazy deletion -- we don't erase old entries,
        // we just ignore them when they surface.
        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            long long new_dist = dist[u] + w;
            if (new_dist < dist[v]) {
                dist[v] = new_dist;
                pq.push({-new_dist, v});  // push new candidate (negated)
            }
        }
    }
    return dist;
}

// Running median using two heaps.
//
// Invariant:
//   lo (max-heap) holds the smaller half of elements.
//   hi (min-heap) holds the larger half.
//   lo.size() == hi.size()  OR  lo.size() == hi.size() + 1
//
// To add x:
//   1. Push x into lo (it might belong there).
//   2. Move lo's top to hi (ensure lo's max <= hi's min).
//   3. If hi got bigger than lo, move hi's top back to lo (rebalance sizes).
//
// Median:
//   If sizes equal, average of lo.top() and hi.top().
//   If lo has one more, lo.top() is the median.
//
struct MedianTracker {
    priority_queue<int> lo;                                // max-heap: lower half
    priority_queue<int, vector<int>, greater<int>> hi;     // min-heap: upper half

    void add(int x) {
        lo.push(x);
        // Ensure every element in lo <= every element in hi.
        hi.push(lo.top());
        lo.pop();
        // Rebalance: lo should have >= hi elements.
        if (hi.size() > lo.size()) {
            lo.push(hi.top());
            hi.pop();
        }
    }

    double median() {
        if (lo.size() > hi.size()) return lo.top();
        return (lo.top() + hi.top()) / 2.0;
    }
};

int main() {
    // --- Demo: Dijkstra ---
    //   0 --2-- 1 --3-- 3
    //   |       |       |
    //   4       1       1
    //   |       |       |
    //   2 --5-- 4 ------+
    int n = 5;
    vector<vector<pair<int,int>>> adj(n);
    auto edge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    };
    edge(0,1,2); edge(0,2,4); edge(1,3,3);
    edge(1,4,1); edge(2,4,5); edge(3,4,1);

    auto dist = dijkstra(0, adj);
    for (int i = 0; i < n; i++)
        cout << "dist[" << i << "] = " << dist[i] << "\n";
    // Output: 0, 2, 4, 4, 3

    cout << "---\n";

    // --- Demo: Running median ---
    MedianTracker mt;
    for (int x : {5, 2, 8, 1, 9}) {
        mt.add(x);
        cout << "add " << x << " -> median = " << mt.median() << "\n";
    }
    // Output: 5, 3.5, 5, 3.5, 5
}

---

Operations Reference

Push and pop are logarithmic, peek is constant, and building from scratch is cheaper than you'd expect.

Operation	Time	Space	Notes
push / insert	$O(\log n)$	$O(1)$ amortized	May trigger vector reallocation
pop / extract top	$O(\log n)$	$O(1)$
top / peek	$O(1)$	$O(1)$
make_heap (build)	$O(n)$	$O(1)$	Floyd's algorithm—not $O(n\log n)$
empty, size	$O(1)$	$O(1)$
Decrease-key	N/A	--	Not supported; use lazy deletion
Overall space	--	$O(n)$	Backed by vector<T>

Problem Patterns & Tricks

Greedy with Heap—"Always Pick the Best"

The loop is always the same: push candidates into a heap, pop the best one, update your state, and push whatever new candidates that decision unlocks. The heap does the bookkeeping so your greedy logic stays clean.

Classic: You have $n$ tasks with deadlines and profits. Schedule to maximize profit—sort by deadline, push profits into a min-heap of size $k$ (number of time slots used so far).

// Greedy job scheduling: pick highest-profit tasks within deadlines
sort(tasks.begin(), tasks.end(), [](auto& a, auto& b){
    return a.deadline < b.deadline;
});
priority_queue<int, vector<int>, greater<int>> pq; // min-heap of selected profits
for (auto& [deadline, profit] : tasks) {
    pq.push(profit);
    if ((int)pq.size() > deadline) pq.pop(); // drop lowest profit if over capacity
}

Problems: CF 1203F2, CF 1474C

K-th Largest / Smallest Element

The trick is counterintuitive: to track the $k$ largest elements, use a min-heap of size $k$. The minimum of that fixed-size set is exactly the $k$-th largest overall, and anything smaller than it gets evicted immediately.

priority_queue<int, vector<int>, greater<int>> pq; // min-heap, size k
for (int x : stream) {
    pq.push(x);
    if ((int)pq.size() > k) pq.pop(); // evict smallest
}
// pq.top() == k-th largest

Problems: CF 1133F, CF 1468J

Merge $k$ Sorted Lists / Streams

At every step, the globally smallest unprocessed element is the smallest among the $k$ current list heads. A min-heap over those heads finds it in $O(\log k)$; popping and re-inserting the next element from that list keeps the heap up to date.

// min-heap of (value, list_index, position_in_list)
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>,
               greater<tuple<int,int,int>>> pq;
for (int i = 0; i < k; i++)
    pq.push({lists[i][0], i, 0});
while (!pq.empty()) {
    auto [val, li, pos] = pq.top(); pq.pop();
    result.push_back(val);
    if (pos + 1 < (int)lists[li].size())
        pq.push({lists[li][pos+1], li, pos+1});
}

Problems: CF 1462E2, CF 1509C

Dijkstra's Algorithm

The canonical heap application: relax edges greedily by current shortest distance. Push (-dist, node) into a max-heap (or (dist, node) into a greater<> min-heap); lazy deletion silently discards stale entries when they surface. See the templates above for the full annotated code.

Problems: CF 20C, CF 1473E

Two-Heap Median Maintenance

Keep the lower half of all elements in a max-heap (lo) and the upper half in a min-heap (hi). After each insertion, rebalance so the heaps differ in size by at most one. The median is lo.top() when sizes differ, or the average of both tops when sizes are equal. See the MedianTracker implementation above.

Problems: CF 1300E, CF 1829G

Lazy Deletion

You can't remove an arbitrary element from a heap—only the top is accessible. The workaround: don't remove it at all. Record it in a separate counter, and the next time it surfaces as top(), quietly discard it and pop again.

priority_queue<int> pq;
unordered_map<int, int> removed; // value -> count to skip

auto lazy_pop = [&]() {
    while (!pq.empty() && removed[pq.top()] > 0) {
        removed[pq.top()]--;
        pq.pop();
    }
};

// To "remove" x without finding it:
removed[x]++;

// To get real top:
lazy_pop();
int real_top = pq.top();

Problems: CF 1354D, CF 1353E

Event-Driven Simulation

In time-based simulation, "process the next event" is exactly what a heap is for. Push events as (time, event_data) into a min-heap; the earliest event always surfaces first, and processing it may generate new events to push.

priority_queue<pair<long long,int>, vector<pair<long long,int>>,
               greater<pair<long long,int>>> events;
events.push({0, start_event});
while (!events.empty()) {
    auto [t, ev] = events.top(); events.pop();
    // process event, possibly generating new events
    events.push({t + delta, new_event});
}

Problems: CF 1525D, CF 1700D

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                  PRIORITY QUEUE / HEAP CHEAT SHEET               |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Repeatedly need max or min element                           |
|   - Dijkstra / shortest path                                     |
|   - Greedy: process best-first                                   |
|   - Median tracking (two heaps)                                  |
|   - DON'T use if you need arbitrary find/remove -> use set       |
+------------------------------------------------------------------+
| KEY STL:                                                         |
|   priority_queue<int> maxpq;            // max on top            |
|   priority_queue<int,vector<int>,greater<int>> minpq;            |
|   pq.push(x); pq.top(); pq.pop();                               |
|   // Negation trick: push -x into max-heap for min behavior      |
+------------------------------------------------------------------+
| COMPLEXITY:                                                      |
|   push    O(log n)    |  top     O(1)                            |
|   pop     O(log n)    |  build   O(n)  [make_heap]               |
|   space   O(n)        |                                          |
+------------------------------------------------------------------+
| GOTCHAS:                                                         |
|   - Default is MAX-heap (largest on top)                         |
|   - greater<T> in template = MIN-heap (confusing but true)       |
|   - No iteration, no find, no decrease-key                       |
|   - Lazy deletion: mark removed, skip when they reach top        |
+------------------------------------------------------------------+

Common Mistakes & Debugging

Max-Heap Default Surprise

The single most common bug: writing priority_queue<int> pq and expecting a min-heap because "priority 1 is the highest priority." But top() returns the largest value. For a min-heap, use:

priority_queue<int, vector<int>, greater<int>> pq;

Or the negation trick: push -x, and top() gives the most-negative (= smallest original) value.

The greater<T> comparator is counterintuitive. greater<int> gives you a min-heap, not a max-heap. The comparator defines how the underlying container orders elements, not what ends up on top. Think of it as: greater means "push greater elements down"—which is exactly what a min-heap does.

No decrease-key. std::priority_queue has no way to update a key already in the heap. Two practical workarounds:

• Lazy deletion: Push a new entry with the updated key; when the old entry surfaces as top(), skip it (check against a dist[] array or a removed set).
• Switch to std::set: It supports erase + insert, giving you effective decrease-key in $O(\log n)$—with slightly higher constant.

Dijkstra with lazy deletion: the if (d > dist[u]) continue; line handles it. If you forget this guard, the same node is relaxed multiple times, potentially leading to $O(V\cdot E)$ time or wrong answers on certain graphs—every lazy-deletion heap pattern needs a staleness guard at the top of the loop.

Integer overflow with pair distances. When using pair<long long, int> in Dijkstra, make sure dist is long long too. A classic WA source on problems with weights up to ${10}^9$ and $n$ up to ${10}^5$.

Empty queue access. Calling top() or pop() on an empty priority_queue is undefined behavior. Always check !pq.empty() first. In a contest under stress, this is an easy segfault to miss.

Custom struct comparison. For a custom struct, define operator< or pass a lambda/functor:

struct Event {
    int time, id;
    bool operator<(const Event& o) const {
        return time > o.time; // min-heap by time (reversed!)
    }
};
priority_queue<Event> pq; // min-time on top due to reversed operator<

The reversal trips everyone up at least once. operator< returning a.time > b.time makes the max-heap treat smaller times as "greater," so they float to the top—giving you the earliest event first.

Duplicate elements. Unlike set, a priority_queue happily stores duplicates. If you push the same element twice (e.g., in Dijkstra), both copies exist. Lazy deletion handles this, but be aware of the extra memory usage: in the worst case, the heap can hold $O(m)$ entries instead of $O(n)$.

"Priority queue = sorted array that updates dynamically." Not even close. A priority queue only guarantees efficient access to the single extreme element (min or max)—nothing else. You cannot iterate in sorted order, look up an arbitrary value, or binary search. If you need any of those, use set/multiset.

    What you CAN see:
    
    priority_queue:  [ ? ? ? ? ? ? 2 ]
                                   ^
                              only this (top)
    
    What you CANNOT see or access efficiently:
    
    sorted view:     [ 2  3  4  5  6  7  9 ]
                       ^  ^  ^  ^  ^  ^  ^
                       all of these are hidden

"I can decrease a key in std::priority_queue." C++ priority_queue has no decrease-key. The standard contest fix is lazy deletion: push a new {better_dist, node}, skip stale entries on pop. Fibonacci heaps have $O(1)$ decrease-key in theory but are never used in CP due to massive constant factors.

"A heap is fully sorted." A heap only maintains the heap property (parent ≤ children for a min-heap). The internal array [2, 3, 4, 7, 5, 6, 9] is NOT sorted—only the root is guaranteed to be the minimum.

    Sorted array:    [2, 3, 4, 5, 6, 7, 9]  <-- every a[i] <= a[i+1]
    Min-heap array:  [2, 3, 4, 7, 5, 6, 9]  <-- only parent <= children
                               ^  ^
                               NOT sorted here (7 > 5)

Bug to recognize at a glance—wrong heap direction:

priority_queue<int> pq; // want shortest distance first
pq.push(5); pq.push(2); pq.push(8);
cout << pq.top(); // prints 8, not 2

Fix: use greater<int> for a min-heap—priority_queue<int, vector<int>, greater<int>> pq;

Self-Test

• [ ] Write the C++ declaration for a min-heap of pair<int,int>—full type with comparator
• [ ] Explain why {dist, node} ordering matters in Dijkstra's PQ—what breaks if you swap the pair order?
• [ ] Implement lazy deletion: push a new entry on update, write the one-line stale-entry guard on pop
• [ ] Describe the build_heap procedure and explain why it runs in $O(n)$, not $O(n\log n)$
• [ ] Name two problems suited for a PQ and two where multiset or monotonic queue is better
• [ ] Explain the two-heap median trick: which elements go in each heap, and how you rebalance
• [ ] State the complexity of push, pop, and top for a binary heap

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Jesse and Cookies	HackerRank	Easy	Basic min-heap usage, repeatedly combine two smallest
2	CF 20C -- Dijkstra?	Codeforces	Easy (1900)	Straightforward Dijkstra with path reconstruction
3	CF 1353E -- K-periodic Garland	Codeforces	Medium (1900)	DP + heap-like optimization for range queries
4	CF 1354D -- Multiset	Codeforces	Medium (1900)	Deletion from a structure—compare heap vs Fenwick
5	CF 1203F2 -- Complete the Projects (hard)	Codeforces	Medium (2100)	Greedy with heap: pick projects by rating change
6	CF 1473E -- Minimum Path	Codeforces	Medium (2000)	Modified Dijkstra with layered states
7	CF 1509C -- The Sports Festival	Codeforces	Medium (1800)	DP with sorted order; heap for greedy subproblems
8	CSES -- Traffic Lights	CSES	Medium	Maintain segments with set (compare heap vs set approach)
9	CF 1700D -- River	Codeforces	Hard (2100)	Simulation / greedy with priority queue scheduling
10	CF 1300E -- Water Balance	Codeforces	Hard (2100)	Stack + greedy merging, heap-style reasoning

For a structured progression, see the Data Structures Practice Ladder.

---

Further Reading

• cp-algorithms: Dijkstra's Algorithm—canonical Dijkstra with priority queue.
• Codeforces Blog: C++ STL Priority Queue—community tips and tricks.
• C++ Reference: priority_queue—full API documentation.
• C++ Reference: Heap operations—make_heap, push_heap, pop_heap, sort_heap.
• For indexed priority queue (decrease-key support), see custom implementations in Dijkstra blog posts on CF.
• For persistent heaps or mergeable heaps (leftist/skew), those are rarely needed below CF 2400.

---

See also: Set and Multiset | Segment Tree | Dijkstra's Algorithm | Data Structure Selection Guide | Practice Ladder