【剑指offer】最小的k个数

class Solution {
public:
    void AdjustHeap(vector<int> &input, int i, int len){
        //i是指从第i个结点开始调整，len是指调整范围0-len
        int child = 2*i + 1;
        int temp = input[i];
        //递归调整法
        if(child < len){//当孩子节点还在调整范围内才可以调整,使用下沉调整
            //把大的数下沉
            if(child + 1 < len && input[child + 1] > input[child]){
                child = child + 1;
            }
            if(input[i] < input[child]){
                swap(input[i], input[child]);
                AdjustHeap(input, child, len);
            }
        }
    /*
    非递归的调整法
        while(child < len){//当孩子节点还在调整范围内才可以调整,使用下沉调整
            //把大的数下沉
            if(child + 1 < len && input[child + 1] > input[child]){
                child = child + 1;
            }
            if(temp >= input[child])
                break;
            input[i] = input[child];
            i = child;
            child = 2*i + 1;
        }
        input[i] = temp;
    */
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        //用sort快排再选数太普通，再复习一遍堆排序,时间复杂度nlogn
        vector<int> res;
        if(input.empty() || k > input.size() || k == 0) return res;
        //建堆
        //算法的思想为维持一个大小为k的最大堆，再对k以后的元素进行遍历，如果有元素比堆顶的元素小的，则交换
        //并且继续调整维持最大堆，这样当遍历完所有元素之后，最大堆里的k个数就是原数组最小的k个数
        //该算法利用最大堆只是为了方便获取最大堆里的最大的元素，并不完全利用堆排序，另一种解法也可以利用堆排序排序完以后再取前k个数
        for(int i = (k - 1)/2; i >= 0; i--){
            AdjustHeap(input, i, k);
        }
        int i = k;
        while(i < input.size()){
            if(input[0] > input[i]){
                swap(input[0], input[i]);
                AdjustHeap(input, 0, k);
            }
            i++;
        }
      for(int i = 0; i < k; i++){
          res.push_back(input[i]);
      }
        return res;
    }
};