Priority queues and heaps

Learning objectives

• Explain the heap property and how priority_queue uses it.
• Use the default max-heap interface.
• Create a min-heap and a custom priority rule.
• Estimate the cost of push, pop, and top.

Prerequisites: vectors, comparison rules, and logarithmic complexity. Review Dynamic sequences with std::vector, Custom comparators, and Complexity first.

What is a heap?

A binary heap is a complete binary tree commonly stored in an array-like structure. In a max-heap, each parent is at least as large as its children, so the largest element is at the root. A min-heap places the smallest element at the root.

Default priority_queue: max-heap

#include <queue>
#include <vector>
std::priority_queue<int> tasks;
tasks.push(4);
tasks.push(10);
tasks.push(7);
int highest = tasks.top(); // 10
tasks.pop();

top() reads the highest-priority value; pop() removes it and returns void. Check empty() before calling top() or pop().

Min-heap

std::priority_queue<int, std::vector<int>, std::greater<int>> smallest_first;
smallest_first.push(4);
smallest_first.push(10);
smallest_first.push(7);
// top() is 4

The third template argument is the comparison type. With std::greater, the smallest value appears at the top.

Custom priority for records

struct Job {
    int priority;
    int id;
};
struct LowerPriorityFirst {
    bool operator()(const Job& a, const Job& b) const {
        return a.priority < b.priority;
    }
};
std::priority_queue<Job, std::vector<Job>, LowerPriorityFirst> jobs;

For priority_queue, the comparator determines heap ordering; the element that comes last under that ordering is exposed by top(). Test custom comparators with small examples to verify which item appears first. The example exposes the job with the greatest numeric priority.

Complexity

Operation	Complexity
top	O(1)
push	O(log n)
pop	O(log n)
Build from a range (constructor)	O(n)

Example: process largest first

while (!tasks.empty()) {
    std::cout << tasks.top() << '\n';
    tasks.pop();
}

This is useful when the next item should be selected by priority rather than arrival order. It appears in scheduling, best-first search, and graph algorithms such as Dijkstra's algorithm.

Common mistakes

• Assuming priority_queue is a min-heap by default.
• Expecting pop() to return the removed value.
• Calling top() on an empty queue.
• Writing a comparator without testing the resulting top element.

Practice

1. Create a min-heap of integers.
2. Process five jobs from highest priority to lowest.
3. What is the complexity of reading top()?
4. Why is a priority queue not a replacement for a fully sorted vector?

Show solutions

1. Use priority_queue<int, vector<int>, greater<int>>.
2. Push all jobs and repeatedly read top then pop.
3. O(1).
4. It exposes only the top item efficiently; it does not provide sorted iteration or arbitrary indexed access.

Summary

A priority queue is a heap-backed adaptor for repeatedly accessing the highest-priority element. Default is max-heap; choose a comparator for other priority rules.

References

• cppreference: priority_queue
• cppreference: heap algorithms