问题：输入n个整数，找出其中最小的k个数。
方案一：将输入的n个整数进行排序，输出前k个数即为所求的k个最小数。时间复杂度为O(nlogn).
方案二：创建一个大小为k的容器，来存储最小的k个数。遍历剩下的n-k个数字，如果大于k个数中的最大值，则替换；否则继续遍历数组的剩 下的数字。
在装k个最小数字的容器(使用大根堆)中，所要做的操作有以下三个：
（1）在k个整数中找到最大的值；（时间复杂度为O(1),根节点即为最大值点）
（2）在这个容器中删除最大的数字；
（3）将可能要插入的值插入到容器中。（插入和删除的时间复杂度为O(logk)）
总共有n个节点，则总的时间复杂度为O(nlogk)。
package com.wyl;
/**
* 找到数组中的k个最小值
* @author wyl
*/
public class KMin {
/**
* 找到数组array中最下的k个数
* 思路：将数组的前K个数当作最小的k个数，存入到数组2中，
* 遍历array中剩余的n-k个数，如果比数组2中的最大数字小，替换数组2中的数字；
* 比其大继续遍历，最后数组2中存放的即为最小的k个数
* @param array
* @param k
* @return
*/
public void findKMin(int[] array, int k){
if(array.length < k){
return;
}
int[] newArray = new int[k];
for(int i=0;i<k;i++){ //前k个数字存入数组中
newArray[i] = array[i];
}
//将数组调整成大根堆,k/2为堆的最后一个非叶节点
for(int i = k/2 - 1;i>=0;i--){
//最后一个非叶节点的下标为n/2-1
rebuildHeap(newArray, i, k);
}
//n-k个数和前面和k中最大数比较
for (int i =k; i < array.length; i++) {
//如果堆顶大于n-k中数,则交换位置
if(newArray[0]>array[i]){
newArray[0]=array[i];
//调整堆,堆顶被替换了,加入被替换的值非常小,会一直下沉到叶子节点.
for(int j = k/2 - 1;j>=0;j--){
//最后一个非叶节点的下标为n/2-1
rebuildHeap(newArray, j, k);
}
}
}
// 输出最小的K个数
for (int i = 0; i < k; i++) {
System.out.print(newArray[i] + " ");
}
}
/**
* 调整堆
* @param a
* @param i
* @param n
*/
public void rebuildHeap(int[] a, int i, int n){
if(n <= 0){
return;
}
int temp = a[i]; //待调整节点
boolean finish = false; //调整完成标志
int li = 2 * i + 1; //左节点下标
while(li <= n - 1 && !finish){
if(li < n - 1 && a[li] < a[li+1]){ //节点存在右子树，且右子树值大于左子树
li = li+1;
}
if(temp < a[li]){ //待调整节点值小于子树值,继续调整子树
a[i] = a[li];
a[li] = temp;
}else{
finish = true;
}
}
}
public static void main(String[] args) {
KMin kMin = new KMin();
int[] array = {4,5,1,6,3,8,7,9};
kMin.findKMin(array, 4);
}
}