/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

void PrintVector(const vector<int>& nums) {
    for (int num : nums) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// Run-time complexity O(nlogn)
// Memory complexity O(1)
// In-place algorithm
/*
void PrintKLargest(vector<int>& nums, const int k) {

    sort(nums.begin(), nums.end(), greater<int>());

    for (int i = 0; i < k; ++i) {
        std::cout << nums[i] << " ";
    }

    std::cout << std::endl;
}
*/

// Run-time complexity O(n)
// Memory complexity O(1)
// In-place algorithm
/*
void PrintKLargest(vector<int>& nums, const int k) {

    make_heap(nums.begin(), nums.end()); //O(3n) -> O(n)

    for (int i = 0; i < k; ++i) {
        std::cout << nums.front() << " ";
        pop_heap(nums.begin(), nums.end() - i); //O(2logn) -> O(logn)
    }

    std::cout << std::endl;
}
*/

// Run-time complexity O(n)
// Memory complexity O(1)
// In-place algorithm
void PrintKLargest(vector<int>& nums, const int k) {

    //O(n)
    priority_queue<int> heap(nums.begin(), nums.end());

    //O(klogn)
    for (int i = 0; i < k; ++i) {
        std::cout << heap.top() << " ";
        heap.pop(); //pop_heap() + pop_back() O(logn) + O(1) -> O(logn)
    }
}


int main()
{
    vector<int> nums = {1, 23, 12, 9, 30, 2, 50};

    int k = 5;

    PrintKLargest(nums, k);

    return 0;
}