Challenge: The k Largest

Lab C++ Beginner 10 points

Read n numbers and k. Using a min-heap of size k, print the k largest from largest to smallest.

Input

Line 1: n k. Line 2: n whole numbers.

Output

k numbers separated by spaces.

Example

Input

8 3
5 12 3 41 7 19 2 33

Output

41 33 19

Sample input available Sample output available

Editor

C++

Hints

Push; if the heap grows past k, pop the smallest.

The heap gives smallest first, so print in reverse.

Solution explanation

The heap never holds more than k items: O(n log k).

Show solution

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();
    }
    vector<int> out;
    while (!pq.empty()) { out.push_back(pq.top()); pq.pop(); }
    for (int i = (int)out.size() - 1; i >= 0; i--) cout << out[i] << (i ? " " : "\n");
    return 0;
}

Output

Answer