题目
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
分析
当有海量的数据的时候，我们可以创建一个容器来存放k个数，然后将剩余的n-k个数，每一个与容器中最大的数进行比较，加入比最大的数大，就进行替换，否则就继续进行比较，直到数组的最后一个元素。
- 思考一
利用何种容器进行存储数据。这里我们选用最大堆。最大堆有一个特征就是父节点的值永远大于孩子节点的值。所以我们每一次只需要与父节点进行比较，然后确定是否替换，最后在调整树的结构（最大堆实际上是一颗二叉树）。
- 思考二
有了以上的思考，更进一步分析，我们只需要将前k-1个数用于最大堆的构建，然后从第k个数开始，进行比较 最终，我们只需要取前k个数就行。
- 思考三
如何构建最大堆，是一个问题。要根据树的性质键堆，树节点的前一半一定是分支节点，它们一定有孩子，因此从这里开始调整初始堆
如下图所示，树节点的前一半一定是分支节点，它们一定有孩子，有五个节点是有孩子的：
综上分析,代码如下：
import java.util.*;
public class Solution {
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;
}
for(int i=k/2-1;i>=0;i--){
buildMaxHeapSort(input,i,k);
}
for(int j=k;j<input.length;j++){
if(input[j]<input[0]){
swap(input,0,j);
buildMaxHeapSort(input,0,k);
}
}
for(int i=k-1;i>=0;i--){
array.add(input[i]);
}
return array;
}
public void buildMaxHeapSort(int[] input,int i,int k){
int leftchild=2*i;
int rightchild=2*i+1;
int larget=i;
if(leftchild<k&&input[i]<input[leftchild]){
larget=leftchild;
}
if(rightchild<k&&input[larget]<input[rightchild]){
larget=rightchild;
}
if(larget!=i){
swap(input,i,larget);
buildMaxHeapSort(input,larget,k);
}
}
public void swap(int[] input,int a,int b){
int temp=input[a];
input[a]=input[b];
input[b]=temp;
}
}
