/**
* 找到无序数组中最小的k个数 时间复杂度O(Nlogk)
* 过程：
* 1.一直维护一个有k个数的大根堆，这个堆代表目前选出来的k个最小的数
* 在堆里的k个元素中堆顶的元素是最小的k个数中最大的那个。
* 2.接下来，遍历整个数组，遍历过程中看当前数是否比堆顶元素小：
* 如果是，就把堆顶元素替换成当前的数，然后从堆顶的位置调整整个堆，让替
* 换操作后堆的最大元素继续处在堆顶的位置；
* 如果不是，则不进行任何操作，继续遍历下一个数；
* 3.在遍历完成后，堆中的k个数就是所有数组中最小的k个数
*/
public class getMinKNumsByHeap { public int[] getMinKNumsByHeap(int[] arr, int k) {
if (k < 1 || k > arr.length) {
return arr;
}
int[] kHeap = new int[k];
for (int i = 0; i < k; i++) {
heapInsert(kHeap, arr[i], i);
}
for (int i = k; i != arr.length; i++) {
if (arr[i] < kHeap[0]) {
kHeap[0] = arr[i];
heapify(kHeap, 0, k);
}
}
return kHeap;
} // 建堆的过程
private void heapInsert(int[] arr, int value, int index) { arr[index] = value;
while (index != 0) {
int parent = (index - 1) / 2;
if (arr[parent] < arr[index]) {
swap(arr, parent, index);
index = parent;
} else {
break;
}
}
} // 调整堆的过程
private void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
while (left < heapSize) {
if (arr[left] > arr[index]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != index) {
swap(arr, largest, index);
} else {
break;
}
index = largest;
left = index * 2 + 1;
right = index * 2 + 2;
}
} // 交换
public void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
}