堆排序及其实现

堆排序

堆是一种叫做完全二叉树的数据结构，可以分为大根堆和小根堆。
大根堆：每个节点的值都大于或者等于它的左右孩子的值
小根堆：每个节点的值都小于或者等于它的左右孩子的值

完全二叉树在数组中的存储

当二叉树按层序遍历的顺序保存在数组中时，**如果根节点存放在array[0]，则节点i的左孩子节点为array[i*2+1]，右孩子节点为array[i*2+2]；如果根节点存放在array[1],则其左孩子为array[i*2],其右孩子为array[i*2+1]**。

建堆过程(大根堆为例)

从最后一个父节点array[n/2]开始，往前遍历，判断父节点和两个孩子节点大小，如果有孩子比父节点还大的，交换，这个交换会导致子树不符合大根堆的特点，因此要再往下再调整子树，直到调整完所有的，就构建好了大根堆
注：其中n是元素的个数。
###代码
堆排序实现找第k大数，采用大根堆的方法

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //建堆
        bigRootHeaps(nums,nums.size());
        //交换k-1个元素去堆底，下一个堆根即为第k大个元素
        for(int i=0;i<k-1;i++)
        {
            //交换
            int temp=nums[0];
            nums[0]=nums[nums.size()-1-i];
            nums[nums.size()-1-i]=temp;
            //调整,只需要调整交换的那个子树即可
            change(nums,0,nums.size()-i-1);
        }
        return nums[0];
    }
    void bigRootHeaps(vector<int>&nums,int len)
    {
        for(int i=len/2;i>=0;i--)
        {
            change(nums,i,len);
        }
    }
    void change(vector<int>&nums,int i,int len)
    {
        int left_child=i*2+1;
        int right_child=i*2+2;
        int largest=i;
        if(left_child<len&&nums[left_child]>nums[i])
        largest=left_child;
        if(right_child<len&&nums[right_child]>nums[largest])
        largest=right_child;
        if(largest!=i){
            int temp=nums[i];
            nums[i]=nums[largest];
            nums[largest]=temp;
            change(nums,largest,len);
        }
    }
};

执行用时：144 ms, 在所有 C++ 提交中击败了14.16%的用户
内存消耗：44.4 MB, 在所有 C++ 提交中击败了65.45%的用户
通过测试用例：39 / 39

效果跟快排旗鼓相当：http://8.130.83.240/article/2023/3/19/9.html

找最大k个元素的堆排序优化

可以采用小根堆而不是大根堆的方式来实现，小根堆只维护k个元素，减少了堆调整的次数
小根堆存放k个元素，根节点存储这k个元素中的最小值
在解决这个问题时:

首先把前k个元素读入堆中，然后维护成一个小根堆；
由于要求最大的前k个值，之后都进来的元素，如果比小根堆的根节点还小，则直接丢弃，因为它不可能是top K元素了；
如果比根节点的元素大，则替换根节点，并调整小根堆，使其符合小根堆的特性；
遍历完所有元素后，小根堆的根节点就是我们要找的第k大个元素；

小根堆解决方法代码实现

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //存放前k个元素的数组
        vector<int>array;
        //初始化数组，先存k个数进去
        for(int i=0;i<k;i++)
        {
            array.push_back(nums[i]);
        }
        //建堆
        smallRootHeaps(array,k);
        for(int i=k;i<nums.size();i++)
        {
            //如果之后的元素甚至比小根堆根节点还小，直接丢掉
            if(nums[i]<=array[0])
            continue;
            else{
                //否则将这个元素放入小根堆根节点
                array[0]=nums[i];
                //调整使其符合小根堆特性
                change(array,0,k);
            }
        }
        return array[0];
    }
    void smallRootHeaps(vector<int>&nums,int len)
    {
        for(int i=len/2;i>=0;i--)
        {
            change(nums,i,len);
        }
    }
    void change(vector<int>&nums,int i,int len)
    {
        int left_child=i*2+1;
        int right_child=i*2+2;
        int min=i;
        if(left_child<len&&nums[left_child]<nums[min])
        min=left_child;
        if(right_child<len&&nums[right_child]<nums[min])
        min=right_child;
        if(min!=i){
            int temp=nums[i];
            nums[i]=nums[min];
            nums[min]=temp;
            change(nums,min,len);
        }
    }
};

执行用时：96 ms, 在所有 C++ 提交中击败了50.23%的用户
内存消耗：46.1 MB, 在所有 C++ 提交中击败了19.67%的用户
通过测试用例：39 / 39

对比使用大根堆，效率提升了一大截，因为除去调整小根堆和建堆的时间，效率接近O(n),但是由于使用了辅助数组，内存占用多了一点，也可以不用辅助数组而直接在nums的前k个位置建小根堆，比较简单，就不实现了。