题解 | #寻找第K大#

刚学会堆排序写的，没有靠自带的优先队列

public:
    void heapInsert(vector<int> &arr,int index)
    {
        while(arr[index]>arr[(index-1)/2]){//该节点比其父节点大 
	        swap(arr[index],arr[(index-1)/2]);
	        index=(index-1)/2; 
        }
    }
    void heapify(vector<int> &arr,int index,int heapsize)
    {
        int left=index*2+1;
        while(left<heapsize){//找孩子可能出现越界情况，所以要检查 
	        int larger=arr[left]>arr[left+1] ? left : left+1;//找出左右孩子中那个较大的
	        larger=arr[larger]>arr[index] ? larger : index;//目的就是找出父亲和两个孩子之间最大的那个
	        if(larger==index){
		        break;
	        }
	        swap(arr[larger],arr[index]);
	        index=larger;
	        left=2*index+1;
        }
    }
    void Heap_Sort(vector<int>& arr)
    {
        vector<int> ret;
        if(arr.size()<2){
	        return;
        }
        for(int i=0;i<arr.size();i++){
	        heapInsert(arr,i);
        }
        int heapsize=arr.size()-1;
        swap(arr[0],arr[heapsize--]);
        while(heapsize>1){
	        heapify(arr,0,heapsize);//每次只需将根节点也就是arr[0]向下heapify即可成大根堆 
	        swap(arr[0],arr[heapsize--]);
        }
    }
    int findKth(vector<int> a, int n, int K) {
        Heap_Sort(a);
        return a[n-K];
    }
};