K Largest Elements

• Find the k largest elements of an unsorted list of length n

When we can store all elements

• How
  1. Insert all the items into a max Priority Queue
  2. Extract the top $k$ elements form the queue
• Time: $O(n+k\log n)$, Space $O(n)$

int kthlargest(vector<int>& nums, int k) {
	// a max heap
	priority_queue<int> pq(nums.begin(), nums.end());
	
	// remove top k-1 elements
	for(int i = k - 1; i > 0; i--) {
		print pq.top();
		pq.pop();
	}
}

For massive data

• Use a min Priority Queue to store k elements and discard the minimum whenever the queue is full and the new element is greater
• Time: $O(n\log k)$, Space: $O(k)$

int kthlargest(vector<int>& nums, int k) {
	// min heap
	priority_queue<int, vector<int>, greater<int>> pq;
 
	for (int i : nums) {
		if(pq.size() > k && i < pq.top())
			continue; 
 
		pq.push(i);
 
		if (pq.size() > k) 
			pq.pop();
	}
 
	print pq;
}