215.数组中的第K个最大元素

class Solution {
public:
    // int findKthLargest(vector<int>& nums, int k) {
        // priority_queue<int> pq(nums.begin(),nums.end());//优先队列或者排序，时间复杂度高
        // int n=k-1;
        // while(n--){
        //     pq.pop();
        // }
        // return pq.top();
    // }
    void adjust(vector<int>&arr,int start,int end){
        int f=start;
        int c=f*2+1;
        while(c<=end){
            if(c+1<=end&&arr[c+1]>arr[c]){
                c++;
            }
            if(arr[f]<arr[c]){
                swap(arr[f],arr[c]);

                f=c;
                c=f*2+1;
            }else{
                break;
            }
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        for(int i=nums.size()/2-1;i>=0;i--){
            adjust(nums,i,nums.size()-1);
        }
        for(int i=nums.size()-1;i>nums.size()-k;i--){//只取k-1次堆顶元素与数组末尾待排序元素交换
            swap(nums[0],nums[i]);
            adjust(nums,0,i-1);
        }
        return nums[0];//调整后的堆顶即为第k大的值

    }
};