template<typename Item>
class MinHeap{
private:
    Item * data;
    int count;// 记录堆中元素个数
    int capacity; // 记录堆中最大可容纳的个数
    void shiftUp(int k){
        while(k>1 && data[k/2]>data[k]){
            swap(data[k/2],data[k]);
            k/=2;
        }
    }
    void shiftDown(int k){
       
        while(2*k<=count){
            int j=2*k;
            if(j+1<=count && data[j+1]<data[j]){
                j++;
            }
            if(data[k]<=data[j]) break;
            swap(data[k],data[j]);
            k=j;
   
        }
    }
public :
    MinHeap(int capacity){
        data=new Item[capacity+1];
        count=0;
        this->capacity=capacity;
    }
    ~MinHeap(){
        delete[] data;
    }
    int size(){
        return count;
    }
    bool isEmpty(){
        return count==0;
    }
    void push(Item item){
        assert(count+1<=capacity);
        data[count+1]=item;
        count++;
        shiftUp(count);
    }
    Item pop(){//extractMin
        assert(count>0);
        Item res=data[1];
        swap(data[1], data[count]);
        count --;
        shiftDown(1);
        return res;
    }
    Item top(){
        assert(count>0);
        return data[1];
    }

};
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        MinHeap<int>minheap = MinHeap<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();i++){
            if(nums[i]<=minheap.top()) continue;
            minheap.pop();
            minheap.push(nums[i]);
            
        }
        return minheap.top();
    }
};