[数据结构与算法]LeetCode 215. 数组中的第K个最大元素（堆实现）

题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思路：从大到小排序，直接输出第k个数即可
使用最小堆的思路：
1.建立一个大小为k的最小堆，并把数组前k个数插入最小堆
2.第k个数后面的数依次与堆顶做比较，如果大于（>）堆顶元素，就把堆顶元素弹出，并把当前数插入堆顶

堆的上滑调整算法（用于插入后的调整）：
将插入位置（i）的元素，与他的父亲结点(i-1)/2进行比较，把两者小的放上面，大的放下面，当i>0时依次重复操作。

堆的下滑调整算法（用于删除后的调整）：
堆元素（位置i）被删除后，该位置将会被当前局部堆的最后面的元素代替，所以要从该位置（i）进行调整，将位置（i）的孩子（i2+1和i2+2）的小者记为j，将位置（i）和位置（j）的元素进行交换，当i*2+1<=N（即有孩子时）时一直重复

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
    /*    使用stl自带的堆
        //priority_queue<int> heap;//默认大根堆，可以插入负数即是小根堆
        priority_queue< int, vector<int>, greater<int> > heap;//小根堆
        int n=nums.size();
        int res;
        for(int i=0;i<k;i++){
            
            heap.push(nums[i]);
        }
        for(int i=k;i<n;i++){
            if((nums[i]) > heap.top()){
                heap.pop();
                heap.push(nums[i]);
            }
        }
        return heap.top();
    */
    int n=nums.size();
    for(int i=0;i<k;i++){
        shiftUp(nums,i);
    }
    for(int i=k;i<n;i++){
        if(nums[i]>nums[0]){
            swap(nums[0],nums[i]);//删除堆顶元素（其实是移动到最后面）,插入heap[i]
            shiftDown(nums,0,k-1);//进行一次下滑调整
        }
        

    }
        return nums[0];
    }
    //自己定义堆
public:
    //若v1<v2则返回true，v1比v2优先级高（若想建立最大堆，反过来即可）
    bool priority_than(int v1,int v2){
        return v1<v2;
    }

    //堆删除操作：即swap(heap[i],heap[0])即可
    //建立堆：依次调用n次上滑调整算法


    void shiftUp(vector<int>& heap,int i){//上滑调整算法,用于插入后调整，不执行插入操作
        while(i>0 && priority_than(heap[i],heap[i-1>>1])){
             swap(heap[i],heap[i-1>>1]);
             i=i-1>>1;
        }
           
    }
    void shiftDown(vector<int>& heap,int i,int N){//下滑调整算法，用于删除后的调整，不执行删除操作
        //参数N表示当前的数组大小
        while(i*2+1<=N){
            int j=i*2+1;//表示将要做交换的
            if(j+1<=N && priority_than(heap[j+1],heap[j])){//找孩子里的最大的
                j++;
            }
            if(priority_than(heap[i],heap[j])){
                break;//i的优先级高则不交换
            }
            else{
                swap(heap[i],heap[j]);
                i=j;
            }

        }
    }
};