【算法】Leetcode第215题堆排序内部原理分析（C++）

1.前言

第一种方法是基于快速排序的选择方法【算法】Leetcode第215题快速排序内部原理分析（C++）。

按照Leetcode官方题解的说法，堆排序是常见的面试问题，所以还是分析一下原理。

排序问题可以使用一种容器适配器即优先级队列，它就是一个“披着队列外衣”的堆，因为优先级队列对外提供的接口只有从队头取元素、从队尾添加元素，再无其他取元素的方式，看起来像一个队列。

默认情况下priority_queue利用max-heap（大项堆）完成对元素的排序。

堆是一棵完全二叉树，数中每个节点值都不小于（或不大于）其左右孩子的值。

如果父节点的值大于或等于左右孩子的值，那就是大项堆；反之则是小项堆。

2.基本原理 2.1构建二叉堆

我们可以用一个完全二叉树去表示数组，根结点在位置0，它的子结点在位置1和2，而子结点的子结点则分别在位置3、4、5、6，以此类推，直到数组元素都用完。

这样形成的二叉树，又称二叉堆。

二叉堆是一组能够用推有序的完全二叉树排序的元素，并在数组中按层级存储。

在下文中，我们将二叉堆称为堆。

在一个堆中，位置k的结点的子结点的位置分别为2k + 1 和 2k + 2。

比如位置1的结点的子结点分别是位置3和位置4。

倘若位置是从1开始，则这个关系变成2k和2k+1。

因为数组的序号从0开始，所以还是用前者的公式表达关系。

一开始的数组是无序的，意味着构建出来的堆也是无序的，那么就需要对堆进行有序化。

2.2 由上至下的推有序化（下沉）

如果堆的有序状态因为某个节点变得比它的子结点更小而被打破，那么我们需要通过交换它和它的子结点较大值来修复堆。

交换后，它可能会也比新的子结点小，所以要继续交换。

这种状态不断地把小的节点往下交换，所以形象地描述为下沉。

当一个结点太小的时候，它需要沉（sink）到堆的更低层。

可以先看看官方题解是如何进行下沉 *** 作的。

    void maxHeapify(vector<int>& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

对于元素a[i]进行判断，求得左孩子和右孩子为2i + 1和2i + 2。

接着要进行越界判断，如果越界了，证明不存在左/右孩子。

largest指向最大的值。

如果这个最大的值并不是a[i], 那就得执行下沉 *** 作，下沉完后调用maxHeapify继续判断是否要继续下沉。

我觉得这里用个循环，让它不断下沉，直到不能再下沉，这样逻辑可能更加清晰。

这是对元素进行遍历，进入maxHeapify判断是否下沉 *** 作，那为什么它是从heapSize/2判断呢？

 void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

首先下沉 *** 作是从下往上的，所以i是递减的。

对于i = heapSize/2，它的两个子结点分别是heapSize + 1和heapSize + 2，明显可见数组已经不存在这两个下标的元素。

所以从heapSize/2的元素时不存在子结点的，也就没有下沉的可能性。

2.3 删除 *** 作

前面已经完成二叉堆的构建，这时元素在堆上已经是有序的，根结点是最大的数。

要想删除最大的元素，先把根结点和最后那个叶子结点交换，因为叶子结点删除了不影响，根节点删除了就乱套了。

叶子结点放在根节点之后，它的大小是不足以坐在根节点的宝座上的，所以需要对它执行下沉 *** 作，让它回到属于它的位置。

        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }

3.整体代码

字母l实现太难看了，换成left。

class Solution {
public:
    void maxHeapify(vector<int>& a, int i, int heapSize) 
        int left = i * 2 + 1, right = i * 2 + 2, largest = i;
        if (left < heapSize && a[left] > a[largest]) {
            largest = left;
        } 
        if ( right < heapSize && a[ right] > a[largest]) {
            largest =  right;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector<int>& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector<int>& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};

部分资料来自《算法 第4版》《代码随想录》
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）