快速选择&堆：

快速选择

核心就是求分隔点的函数：

int split(vector<int>&nums,int start,int end){
    int i = start;
    int j = start;
    while(i<end){
        if(nums[i]<nums[end]){
            swap(nums[i],nums[j++]);
        }
        i++;
    }
    swap(nums[j],nums[end]);
    return j;
}

可以引申出快排

void quick_sort(vector<int>&nums,int start,int end){
    if(start>=end)return; 
    int i = split(nums,start,end);
    quick_sort(nums,start,i-1);
    quick_sort(nums,i+1,end);

}

topk

void topk_partition(vector<int>&nums,int start,int end,int k){
    int partition = split(nums,start,end);
    //大于=partition的元素个数是end-partition+1
    if(end-partition+1==k)return ;
    if(end-partition+1<k){//topk 需要往左遍历
        topk_partition(nums,start,partition-1,k-(end-partition+1));   
    }else topk_partition(nums,partition+1,end,k);
}

void topk(vector<int>&nums,int k){
    topk_partition(nums,0,nums.size()-1,k);
}

堆：

堆的核心操作是调整堆：
调整堆是自上而下的过程

void heapify(vector<int>&nums,int i,int sz){
    //调整
    int tmp = nums[i];//只调整根元素所在的位置 都是从上到下的
    while((2*i+1)<sz){
        int child = 2*i+1;//考虑i=0可解
        //大顶堆
        if((2*i+2)<sz&&nums[child]<nums[child+1])child = child+1;
        if(nums[child]>tmp){
            nums[i] = nums[child];
            i = child;
        }else break;
    }
    nums[i] = tmp;
}

引申出堆排：
1.自下而上的构建堆
2.每次将堆顶元素移出之后调整堆

void heap_sort(vector<int>&nums){
    for(int i = nums.size()/2-1;i>=0;i--){//遍历过程是自下而上的
        heapify(nums,i,nums.size());//从第一个非叶子节点开始构建堆
    }
    for(int i = nums.size()-1;i>0;i--){
        swap(nums[0],nums[i]);
        heapify(nums,0,i);
    }
}

topk:

void topk(vector<int>&nums,int k){
    for(int i = k/2-1;i>=0;i--){
        heapify(nums,i,k);//topk应该设置为小顶堆 这里做一个low-k吧
    }
    for(int i = k;i<nums.size();i++){
        if(nums[i]<nums[0]){
            swap(nums[i],nums[0]);
            heapify(nums,0,k);
        }
    }
}