题解 | #排序#

    //手写的堆排序 
    //1、构建小跟堆 
    //2、交换之后 再从根节点开始调整
    void adjust_heap(vector<int> &input, int i, int size) {
        int tp = input[i]; //tp保存根节点的值
        int k; 
        //假设i是从根节点0开始调整，当根节点的左右字树调整完之后，再应该调整k=3索引开始调整，这时的父节点应该是1索引的位置
        for(k = 2 * i+1; k < size; k = 2 * k + 1) {
            if(k + 1 < size && input[k+1] < input[k]) {
                k++; //k指向子树中最小的节点位置
            }
            if(input[k] < tp) { //如果根节点大于左右子树
                input[i] = input[k]; //把子节点覆盖根节点
                i = k; //i指向上面tp根节点需要交换的位置
            } else { //表示i节点位置是符合小跟堆的  直接跳出循环 后面看其它位置符不符合
                break;
            }
        }
        input[i] = tp; //将其根节点插入到合适的位置
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        //先将数组中的所有元素调整为小跟堆
        for(int i = input.size()/2-1; i >= 0; i--) {
            adjust_heap(input, i, input.size());
        }
        for(int i = input.size()-1; i >= 0 && k > 0; k--, i--) {
            swap(input[0], input[i]); //交换头尾节点 继续调整根节点为小根堆
            res.push_back(input[i]);
            adjust_heap(input, 0, i);
        }
        cout<<res.size()<<endl;
        return res;
    }
    //使用容器中的优先队列  底层也是堆排序
    vector<int> GetLeastNumbers_Solution1(vector<int> input, int k) {
        priority_queue<int, vector<int>, greater<int>> prior; //默认是大跟堆，需要调整为小跟堆
        vector<int> res;
        if(input.size() <= 0)
            return res;
        for(int item : input) {
            prior.push(item);
        }
        while(k > 0) {
            res.push_back(prior.top());
            prior.pop();
            k--;
        }
        return res;
    }