#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

bool compare(int a, int b)
{
	// child > parent
	return a > b;
}

// Time complexity: O(n*lgk)
vector<int> getLargestK(const vector<int>& input, size_t k)
{
	vector<int>::const_iterator itLeft = input.begin() + k;
	vector<int> heap(input.begin(), itLeft);
	make_heap(heap.begin(), heap.end(), &compare);
	//copy(heap.begin(), heap.end(), ostream_iterator<int>(cout, " "));
	//cout << endl;

	for(vector<int>::const_iterator it = itLeft; it != input.end(); ++it)
	{
		if(compare(*it, heap[0]))
		{
			pop_heap(heap.begin(), heap.end(), &compare);
			heap[k-1] = *it;
			push_heap(heap.begin(), heap.end(), &compare);
			//copy(heap.begin(), heap.end(), ostream_iterator<int>(cout, " "));
			//cout << endl;
		}
	}

	copy(heap.begin(), heap.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	return heap;
}

int main()
{
	int array[] = {1, 2, 3, 4, 5, 8, -1, 3, 6};
	vector<int> input(array, array+sizeof(array)/sizeof(array[0]));

	getLargestK(input, 1);

	getLargestK(input, 2);

	getLargestK(input, 3);

	getLargestK(input, 4);

	getLargestK(input, 5);

	getLargestK(input, 6);

	getLargestK(input, 7);

}