The k largest numbers
n numbers (n ≤ 106) and a number k are read. Print the k largest, from the largest to smaller ones, using memory for only k numbers.
Example
Input
7 3
5 1 9 3 7 9 2Output
9 9 7A priority queue always gives the element with the highest (or lowest) priority, and adding and removing take only O(log n). It is used in Dijkstra's algorithm, for choosing "the next best one" and in many greedy algorithms.
| Operation | Meaning | Complexity |
|---|---|---|
pq.push(x) | adds an element | O(log n) |
pq.top() | returns the element with the highest priority (does not remove it) | O(1) |
pq.pop() | removes that element | O(log n) |
pq.size(), pq.empty() | the number of elements, whether it is empty | O(1) |
Inside there is a heap – a tree in which every parent is larger than its children, so the largest element is always at the root. The header is <queue>.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> maxHeap; // by default: the largest on top
priority_queue<int, vector<int>, greater<int>> minHeap; // the smallest on top
for (int x : {5, 1, 8, 3}) {
maxHeap.push(x);
minHeap.push(x);
}
while (!maxHeap.empty()) { cout << maxHeap.top() << " "; maxHeap.pop(); }
cout << "\n";
while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); }
cout << "\n";
return 0;
}
Output:
8 5 3 1
1 3 5 8
If the queue holds pairs pair<int,int>, they are compared first by the first element, then by the second. A common trick: put the priority in the first element and the data (e.g. a graph node) in the second. A min-heap of pairs is written as priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> – that is exactly what the queue in Dijkstra's algorithm (SR) looks like.
For a more complex criterion you write a structure with a comparison operator; be careful, the logic is "reversed": the element for which the comparison returns true goes lower.
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
n numbers (n ≤ 106) and a number k are read. Print the k largest, from the largest to smaller ones, using memory for only k numbers.
7 3
5 1 9 3 7 9 29 9 7We have n pieces of rope of given lengths. Joining two pieces of lengths a and b costs a + b and gives a piece of length a + b. What is the lowest cost of joining all the pieces into one?
4
4 3 2 629Jobs arrive over time: job i arrives at the moment t[i], lasts d[i] and has the priority p[i]. The processor runs one job at a time until it is finished; when it is free, it chooses among the jobs that have arrived the one with the highest priority (for the same priority – the one that arrived earlier). Print the order of execution (numbers from 1).
4
0 3 1
1 2 5
2 1 3
3 2 51 2 4 3priority_queue is a max-heap; for the smallest element on top add vector<T>, greater<T>.top() on an empty queue is an error – always check empty() first.multiset.1. Which element does top() return for priority_queue<int>?
2. What is the complexity of the operation push?
3. Which queue is needed for Dijkstra's algorithm?