堆排序

class Solution {
public:
    vector<int> h;
    int idx;

    void down(int u) {
        int t = u;
        if (u * 2 <= idx && h[u * 2] > h[t])
            t = u * 2;
        if (u * 2 + 1 <= idx && h[u * 2 + 1] > h[t])
            t = u * 2 + 1;
        if (t != u) {
            swap(h[t], h[u]);
            down(t);
        }
    }

    vector<int> GetLeastNumbers_Solution(vector<int> v, int k) {
        if (k > v.size())
            return {};
        h = vector<int>(k + 1);

        for (int i = 0; i < k; i ++ )
            h[i + 1] = v[i];

        idx = k;
        for (int i = k / 2; i > 0; i -- )
            down(i);

        for (int i = k; i < v.size(); i ++ ) {
            if (v[i] < h[1]) {
                h[1] = v[i];
                down(1);
            }
        }

        vector<int> ans(k);
        for (int i = 0; i < k; i ++ )
            ans[i] = h[i + 1];
        return ans;
    }
};