最小的K个数

转载学习：https://www.cnblogs.com/lingongheng/p/6444226.html

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

知识点：

• 最大堆和最小堆是二叉堆的两种形式。
  • 最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
  • 最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

思路：堆排序，构建最大堆，实现时间复杂度O(n*logk);

• 1.构建前k个元素构造成最大堆；

• 2.遍历下标在k以后的数组，与堆顶比较，如果小于堆顶，置换二者，并重新构建最大堆，否则不处理；

• 3.将k之前的元素从小到大加入集合，返回集合；

  public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    ArrayList<Integer> array = new ArrayList<Integer>();
    if (input == null || input.length == 0 || k <= 0 || k > input.length) {
        return array;
    }
    int length = input.length;
    // 1.构建最大堆
    for (int i = k / 2 - 1; i >= 0; i--) {
        buildMaxHeap(input, i, k);
    }
    // 2.对比k之后元素，若小于堆顶值，交换二者，并重新构建最大堆
    for (int i = k; i < length; i++) {
        if (input[i] < input[0]) {
            swap(input, i, 0);
            buildMaxHeap(input, 0, k);
        }
    }
    // 3.将最小的k个数，从小到大加入集合
    for (int i = k-1; i >= 0; i--) {
        array.add(input[i]);
    }
    return array;
  }
  
  private void buildMaxHeap(int[] input, int i, int k) {
  
    int leftChild = 2 * i;
    int rightChild = 2 * i + 1;
    int large = i;
  
    if (leftChild < k && input[leftChild] > input[large]) {
        large = leftChild;
    }
  
    if (rightChild < k && input[rightChild] > input[large]) {
        large = rightChild;
    }
  
    // 将最大值向前移动，i所对应的值，移动到没有比它大的值将停止移动
    if (large != i) {
        swap(input, i, large);
        buildMaxHeap(input, large, k);
    }
  }
  
  private void swap(int[] input, int i, int large) {
    int temp = input[i];
    input[i] = input[large];
    input[large] = temp;
  }