题解 | #寻找第K大#

堆排序求第K大的值，完美符合题目要求。

但第一次提交有一例没过，打印循环中的最大输出后发现6878这个答案莫名其妙消失了，得出的错误答案是270，但前面的输出是降序，一脸懵逼。。。看了十分钟，怀疑是不是MaxHeap函数的for循环起始点不对，我一开始设置的起始点是i=size-3，意思是排除最后两个结点，也许是这个样例刚好堆到最后就两个数，6878和270，结果最后直接跳过了，没有维护，所以输出的是当前堆顶270。

class Solution {
  public:
    void MaxHeap(vector<int>& v) { //维护最大堆
        int size = v.size();
        int max_child, tmp; //max_child记录更大的子节点的索引
        for (int i = size-1; i >= 0; i--) {
            if (2 * i + 1 < size) { //有左子节点
                if (2 * i + 2 < size) { //有右子节点
                    max_child = (v[2 * i + 1] > v[2 * i + 2]) ? (2 * i + 1) : (2 * i + 2);
                } else {
                    max_child = 2 * i + 1;
                }
                if (v[i] < v[max_child]) {
                    tmp = v[i];
                    v[i] = v[max_child];
                    v[max_child] = tmp;
                }
            }
        }
    }
    int HeapSort(vector<int>& v, int k) { //每次输出当前最大值，并与堆底值交换后排除
        for (int i = 0; i < k; i++) {
            MaxHeap(v);
            if (i == k - 1) break;
            swap(v[0], v[v.size() - 1]);
            v.pop_back();
        }
        return v[0];
    }
    int findKth(vector<int>& a, int n, int K) {
        if (!n) return 0;
        return HeapSort(a, K);
    }
};