描述：在一個(gè)包含 n 個(gè)數(shù)據(jù)的數(shù)組中抠蚣，查找前 K 大數(shù)據(jù)。
1.思路
維護(hù)一個(gè)大小為 K 的小頂堆面殖，順序遍歷數(shù)組竖哩，從數(shù)組中取出數(shù)據(jù)與堆頂元素比較。如果比堆頂元素大脊僚，就把堆頂元素刪除相叁，并且將這個(gè)元素插入到堆中；如果比堆頂元素小辽幌，則不做處理增淹，繼續(xù)遍歷數(shù)組。這樣等數(shù)組中的數(shù)據(jù)都遍歷完之后乌企，堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了虑润。
2.代碼實(shí)現(xiàn)
public class TopK {
private int[] nums;//原始靜態(tài)數(shù)據(jù)
private int[] smallHeap;//小根堆
public TopK(int[] origin) {
this.nums = origin;
}
//從1開(kāi)始存儲(chǔ)數(shù)據(jù)，0位置廢棄
public int[] getTopK(int k) {
if (nums == null || nums.length < 2|| k >= nums.length) {
return null;
}
this.smallHeap = new int[k + 1];
buildHeap(k);
return smallHeap;
}
//構(gòu)建大小為k的小根堆
private void buildHeap(int k) {
//初始化
for (int i = 1; i <= k; i++) {
smallHeap[i] = nums[i];
}
//構(gòu)建初始小根堆
for (int i = smallHeap.length / 2; i >= 1; i--) {
heapify(smallHeap, i, smallHeap.length - 1);
}
//繼續(xù)插入其他元素完成小根堆構(gòu)建
for (int i = k+1; i < nums.length; i++) {
if (nums[i] > getTop()) {//如果數(shù)據(jù)大于小根堆的最小值,插入
insert(nums[i]);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private void heapify(int[] nums, int i, int n) {
int left = 2 * i;
int right = 2 * i + 1;
while (true) {
int min = i;
min = left <= n && nums[left] < nums[i] ? left : i;
min = right <= n && nums[right] < nums[min] ? right : min;
if (min == i) {
break;
}
swap(smallHeap, i, min);
i = min;
left = 2 * i;
right = 2 * i + 1;
}
}
public void insert(int value) {
smallHeap[1] = value;//刪除堆頂元素加酵，插入新元素
heapify(smallHeap, 1, smallHeap.length - 1);
}
/**
* 返回堆頂元素
*
* @return
*/
public int getTop() {
return smallHeap[1];
}
public static void main(String[] args) {
int[] nums = {-1, 3, 4, 1, 2, 5, 10, 11, 99, 88, 22, 20, -11};
TopK topK = new TopK(nums);
int[] res = topK.getTopK(5);
for (int i = 1; i < res.length; i++) {
System.out.println(res[i]);
}
}
}
