C++ priority_queue

In this page:

What is priority_queue?
push(), pop() and top()
Max-heap vs Min-heap
Custom Comparators
Practical Use: Top-K Elements

What is priority_queue?

std::priority_queue is a container adapter that always keeps the largest element accessible at the top, implemented internally as a binary heap (a max-heap by default). It is used whenever you repeatedly need the current maximum (or minimum) from a changing collection.

Example: What is priority_queue?

cpp

#include <iostream>
#include <queue>

int main() {
	std::priority_queue<int> pq; // largest element always accessible at top
	pq.push(3);
	pq.push(7);
	pq.push(1);
	std::cout << pq.top() << std::endl;
	return 0;
}

push(), pop() and top()

push() inserts an element and re-heapifies. top() returns the highest-priority element without removing it. pop() removes the top element, after which the next-highest element becomes the new top.

Example: push(), pop() and top()

cpp

#include <iostream>
#include <queue>

int main() {
	std::priority_queue<int> pq;
	pq.push(5);
	pq.push(9);
	std::cout << pq.top() << std::endl; // highest priority, no removal
	pq.pop();
	std::cout << pq.top() << std::endl;
	return 0;
}

Max-heap vs Min-heap

By default, priority_queue is a max-heap (largest on top). To get a min-heap (smallest on top), specify the underlying container and use std::greater as the comparator.

Example: Max-heap vs Min-heap

cpp

#include <iostream>
#include <queue>
#include <vector>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // smallest on top
	minHeap.push(5);
	minHeap.push(1);
	minHeap.push(3);
	std::cout << minHeap.top() << std::endl;
	return 0;
}

Custom Comparators

A priority_queue can order elements by any rule by supplying a custom comparator (a function object or lambda-based struct), such as ordering objects by a specific field.

Example: Custom Comparators

cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>

struct CompareAbs {
	bool operator()(int a, int b) { return abs(a) < abs(b); }
};

int main() {
	std::priority_queue<int, std::vector<int>, CompareAbs> pq;
	pq.push(-10);
	pq.push(3);
	std::cout << pq.top() << std::endl;
	return 0;
}

Practical Use: Top-K Elements

A common priority_queue pattern is finding the k largest (or smallest) elements in a stream of data without sorting the whole collection.

Example: Practical Use: Top-K Elements

cpp

#include <iostream>
#include <queue>
#include <vector>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; // keep only the 2 largest
	int values[] = {5, 1, 9, 3};
	for (int v : values) {
		minHeap.push(v);
		if (minHeap.size() > 2) minHeap.pop();
	}
	std::cout << minHeap.top() << std::endl;
	return 0;
}

🔒

Chapter Quiz — Complete all 15 topics to unlock

0/15 topics done

Complete these topics first:

← Previous Lesson C++ queue STL Next Lesson → C++ Memory Management