All lessons
LESSON 40/53Ready-made Containers
Priority Queue
GOALAlways take the largest — or the smallest — next.
Sometimes you need "the biggest one left", over and over. Re-sorting each time is slow. A priority_queue always keeps the biggest on top, and both adding and taking cost log n.
ON THIS PAGE
SHOW EXAMPLE IN
//THE EXAMPLE
main.cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> big;
big.push(5);
big.push(1);
big.push(9);
cout << big.top() << endl;
big.pop();
cout << big.top() << endl;
priority_queue<int, vector<int>, greater<int>> small;
small.push(5);
small.push(1);
small.push(9);
cout << small.top() << endl;
return 0;
}> what you see
9 5 1
//LINE BY LINE
Watch it run
priority_queue<int> big. Push 5.
The two languages default opposite ways
Miss this difference and your algorithm runs backwards — no error, just a wrong answer.
| Language | On top by default | How to flip it |
|---|---|---|
C++ priority_queue | Хамгийн ИХ / the LARGEST | greater<int> |
Python heapq | Хамгийн БАГА / the SMALLEST | Сөрөг утга хийх / push negatives |
priority_queue<int> big; // largest on top
priority_queue<int, vector<int>, greater<int>> small; // smallest on topPutting your own struct in the queue
Dijkstra needs a pair of "distance, node". To get the smallest distance on top you have to say what to compare by.
// pair compares by .first, so put the distance there
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({0, start}); // {distance, node}The queue compares by the FIRST field. Put the node first and it orders by node number instead of distance — and your algorithm is quietly wrong.