题解 | 寻找第K大

class Solution {
public:
    vector<int> heap;
	//堆：每个根节点大于（小于）左右子节点，形成大根堆（小根堆），
    void down_go(int start){  //向下调整
        int smallest = start;
        int L = smallest*2 +1;
        int R = smallest*2 +2;

        if(L<heap.size() && heap[smallest] > heap[L]) smallest = L;
        if(R<heap.size() && heap[smallest] > heap[R]) smallest = R;  

        if(smallest != start){  //维护根节点最小
            swap(heap[smallest], heap[start]);
            down_go(smallest);   //向下递归
        }
    }

    void up_go(int start){ //加入新元素，向上调整
        //while(start){
            int father = (start-1)/2;
            if(heap[father] > heap[start]){
                swap(heap[father], heap[start]);
                start = father;
				up_go(start); //只用调整新加入的节点和父节点的关系；
            }
	  		//else{
            //    break;
            //}
        //}
    }

    int findKth(vector<int>& a, int n, int K) {
        // write code here

        for(int i=0; i<n; ++i){
            if(heap.size()< K){
                heap.push_back(a[i]);
                up_go(i);
            }else{
                if(a[i] > heap[0]){
                    heap[0] = a[i];
                    down_go(0);
                }
            }
        }
        return heap[0];
    }


};