215. Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        priority_queue<int, vector<int>, greater<int>> minheap;
        for(int i =0; i<k; i++){
            minheap.push(nums[i]);
        }

        for(int i=k; i<=nums.size()-1; i++){
            if(nums[i]>minheap.top()){
                minheap.pop();
                minheap.push(nums[i]);
            }
        }
        
        return minheap.top();
    }
};

 

 

1.create a min heap using priority queue. first parameter int is identifying the type of the variables in the heap. second parameter shows the storage box of the variable being stored. third parameter is a comparison function chaning how the queue sorts it self. by default priority queue creates max heap but using greater<int>, min heap is created.

 

2. for first k elements in the array, push it to the min heap. where the top() of the heap is the minimum value. and from k to the rest of the elements, if the element is bigger than the smallest element in the heap, pop the heap, then push the element.

 

3.minheap.top() will be the kth largest element in the end.