Priority Queues
A queue serves values in the order they arrived. Sometimes the order of arrival does not matter, and you want the most important value first. A hospital treats the most serious case first, not the patient who came first. For this, C++ has the priority queue: top() always gives you the largest value. It is in the same <queue> header as queue.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(5);
pq.push(1);
pq.push(8);
pq.push(3);
cout << pq.top() << "\n";
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << "\n";
return 0;
}
Output:
8
8 5 3 1
A priority queue has the same push, top, pop, empty and size as a stack. The difference is which value is on top. After each pop, the next largest value moves to the top, so the loop printed the values from largest to smallest.
Inside, a priority queue does not keep all its values sorted. It keeps them in a shape called a heap, which only makes sure the largest value is on top. That is less work than sorting, so push and pop stay fast even with millions of values. Because the largest value is on top, this is called a max-heap.
Smallest on top
To get the smallest value on top instead, you write a longer type:
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5);
pq.push(1);
pq.push(8);
pq.push(3);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << "\n";
Output:
1 3 5 8
The type has three parts:
| Part | Meaning |
|---|---|
int | the type of the values |
vector<int> | where the values are stored; always write a vector of the same type |
greater<int> | the rule; it puts the smallest value on top |
This is called a min-heap. You cannot give only the first and the third part, so vector<int> must always be there in the middle.
The k largest numbers
A common interview question is: find the k largest numbers in a list. One way is to push every number into a max-heap and pop k times. A better way uses a min-heap that never holds more than k numbers. After each push, if the heap has more than k numbers, pop the smallest one. Small numbers keep getting thrown out, and at the end only the k largest are left.
vector<int> nums = {5, 1, 8, 3, 9, 2};
int k = 3;
priority_queue<int, vector<int>, greater<int>> best;
for (int x : nums) {
best.push(x);
if (best.size() > k) {
best.pop();
}
}
cout << best.top() << "\n";
Output:
5
The heap now holds 5, 8 and 9, the three largest numbers. The smallest of them, 5, is on top, so best.top() is the third largest number in the list. The heap never held more than 4 numbers, even if the list had a million.
In the exercise, use a min-heap like this one to print the k largest numbers from smallest to largest.