题解 | #第k轻的牛牛#

知识点：

排序/堆排序

分析：

可以使用快速排序，各种排序方法，这里使用堆排序

堆排序，重点理解：

i为什么从n/2开始down？

首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。

开始创建堆的时候，元素是随机插入的，所以不能从根节点开始down，而是要找到满足下面三个性质的结点：

1.左右儿子满足堆的性质。

2.下标最大（因为要往上遍历）

3.不是叶结点（叶节点一定满足堆的性质）

编程语言：

C++

完整代码：

    void down(int u, int s_h, int* heap) {
        int t = u;
        if (2 * u <= s_h && heap[2 * u] > heap[t]) t = 2 * u;
        if (2 * u + 1 <= s_h && heap[2 * u + 1] > heap[t]) t = 2 * u + 1;
        if (u != t) {
            swap(heap[u], heap[t]);
            down(t, s_h, heap);
        }
    }
    void hsort(vector<int>& nums, int k) {
        int size_h = nums.size();
        int heap[size_h + 1];
        for (int i = 1; i <= size_h; i++) {
            heap[i] = nums[i - 1];
        }
        for (int i =  size_h / 2 ; i; i--) down(i, size_h, heap);
        int n = size_h;
        int i = 0;
        while (n--) {
            nums[i++] = heap[1];
            heap[1] = heap[size_h--];
            down(1, size_h, heap);
        }
    }
    int findKthSmallest(vector<int>& weights, int k) {
        hsort(weights,k);
        return weights[weights.size() - k];
    }