Priority queues: choose the next extreme
Use max-heaps, min-heaps, and pair priorities without confusing heap order with full sorting.
Highest priority is not earliest arrival
std::priority_queue<int> exposes the greatest stored integer at top(). push inserts, pop removes one top occurrence, and size/empty inspect the state. Duplicates remain separate. top() reads without removing and provides read-only access to the key.
The adaptor has no general indexing, iteration, front/back, arbitrary erase, or direct priority update. Its heap structure guarantees the next extreme at the top; it does not expose a fully sorted internal array.
The comparator changes the selected end
A min-heap uses std::priority_queue<int, std::vector<int>, std::greater<int>>. Include <functional>, <queue>, and <vector>. push, pop, and top keep their names; the smallest value now has highest priority.
Pair ordering still applies. A default max-heap of (score, ID) prefers larger score and then larger ID. A min-heap of (time, ID) prefers smaller time and then smaller ID. Neither automatically implements higher score with smaller ID. A bounded key such as (score, −ID) can express that mixed rule only when negation is safe and the tie direction is checked.
// Complete C++23 program. No input; output: 9 2
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> greatest;
std::priority_queue<int, std::vector<int>, std::greater<int>> smallest;
for (int x : {4, 9, 2, 9}) {
greatest.push(x);
smallest.push(x);
}
greatest.pop(); // Removes only one nine.
std::cout << greatest.top() << ' ' << smallest.top() << '\n';
}Count the updates, not just top()
top() is O(1). Heap repair for push and pop uses logarithmic comparisons. A single push may also trigger a linear reallocation of the default backing vector, so the usual O(log(n + 1)) push time is amortized over a sequence.
Building by n pushes and extracting all values takes O(1 + n log(n + 1)) time. If fixed input only needs sorted output once, vector plus sort is often simpler. A heap is especially useful when insertions alternate with requests for the current minimum or maximum.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
A default max-priority queue of pairs contains (90, 2) and (90, 5). Which is top?
Turn the idea into code
Read n events as time ID, with nonnegative times and unique positive IDs. Print IDs in earlier-time order and smaller-ID order on ties. Use a min-priority queue of pairs; n may be zero.
Give me a hint
Store the fields as (time, ID), and use std::greater for that same pair type.
Show the explained solution
The minimum pair is exactly the earliest event with the required tie rule. Copy the top before popping. Individual pushes and all removals take O(1 + n log(n + 1)) total amortized time, with O(n + 1) storage.
// Complete C++23 program. Input: 0 <= n <= 200000, then time ID pairs.
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
int main() {
int n = 0;
std::cin >> n;
using Event = std::pair<int, int>;
std::priority_queue<Event, std::vector<Event>, std::greater<Event>> events;
for (int i = 0; i < n; ++i) {
int time = 0, id = 0;
std::cin >> time >> id;
events.push({time, id});
}
while (!events.empty()) {
Event next = events.top();
events.pop();
std::cout << next.second << '\n';
}
}Your notes
Mark complete when you can explain it yourself.