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）
