Find the largest few numbers from a list.
What to build
A program that uses a priority queue instead of sorting.
Requirements
- Read
n,kand the numbers. - Print the
klargest, from largest to smallest, separated by single spaces. - If there are fewer than
knumbers, print all of them.
Input
The first line has n and k. The second line has n whole numbers.
Output
One line.
Constraints
n is from 1 to 100000 and k is from 1 to 100000.
Example
Input:
5 2
3 9 2 7 4
Output:
9 7
Why it works
Taking the top k times costs far less than sorting everything when k is small, because a heap only does the work that is needed.
Examples
Example 1 · Input
5 2 3 9 2 7 4
Expected output
9 7
Example 2 · Input
2 5 1 2
Expected output
2 1
Hints
Hint 1
A priority_queue gives the largest item first.
Hint 2
Handle k being larger than n.
Hint 3
Read top, then pop, k times.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
}
bool first = true;
for (int i = 0; i < k && !pq.empty(); i++) {
if (!first) cout << " ";
cout << pq.top();
pq.pop();
first = false;
}
cout << endl;
return 0;
}