Priority Queue

A priority queue returns the highest- or lowest-priority item rather than the oldest item, commonly using a heap.

What to understand

ADT versus implementation
std::priority_queue
Custom comparators
Scheduling and graph algorithms

Remember this

1C++ priority_queue is a max-heap by default
2Use greater<T> for a min-heap
3Dijkstra repeatedly extracts the smallest distance

Detailed notes

A priority queue is an abstract data type; a heap is its common implementation. Items leave according to priority, with arrival order relevant only if the design explicitly includes a stable tie-breaker.

std::priority_queue exposes the largest item under its comparator by default. Custom records require a comparator that establishes strict weak ordering and often include sequence numbers for deterministic ties.

How it works

1Define whether smaller or larger values mean higher priority.
2Choose a comparator consistent with that definition.
3Push every new item and inspect only top for the next item.
4Store lazy duplicate entries when decrease-key is unavailable and skip stale ones later.

Where it is used

CPU and event scheduling
Dijkstra, Prim, and best-first search
Merging sorted streams and top-k queries

Common mistakes

Calling it FIFO
Reversing custom comparator logic
Mutating an item's priority after it is already inside the heap

Complexity analysis

Operation	Best	Average	Worst	Extra space
top	O(1)	O(1)	O(1)	O(1)
push	O(log n)	O(log n)	O(log n)	O(1)
pop	O(log n)	O(log n)	O(log n)	O(1)

C++ implementation

C++17 reference

C++ max-heap and min-heap

The comparator states which element has lower priority; greater<int> therefore exposes the minimum.

#include <functional>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int> maximumFirst;
priority_queue<int, vector<int>, greater<int>> minimumFirst;

for (int value : {7, 2, 9, 4}) {
    maximumFirst.push(value);
    minimumFirst.push(value);
}

cout << maximumFirst.top() << '\n'; // 9
cout << minimumFirst.top() << '\n'; // 2

15 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.