0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 使用最小堆解决海量数据数据中求TopK最大的几个数问题

codingcoge 2019-03-30 11:54:17 浏览488

### 求一亿个数据中最大的100个数.

注意:
(数组长度)/2-1代表下标最大的那个有子节点的父节点位置.

//最小堆
class MinHeap{
//最小堆维持的大小
private int[] data;
public MinHeap(int[] data){
this.data = data;
buildHeap();
}
//建立最小堆
private void buildHeap(){
for(int i=(data.length)/2-1;i>=0;i--){
heapify(i);
}
}
private void heapify(int i){
int left = left(i);
int right = right(i);
int small = i;
if(left<data.length&&data[left]<data[small]){
small = left;
}
if(right<data.length&&data[right]<data[small]){
small = right;
}
if(i == small){
return;
}
swap(i,small);
heapify(small);
}
private void swap(int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] =temp;
}
private int left(int i){
return ((i+1)<<1)-1;
}
private int right(int i){
return (i+1)<<1;
}
public int getRoot(){
return data[0];
}
public void setRoot(int root){
data[0] = root;
heapify(0);
}
}
public class Main {

public static void main(String[] args) {
int[] number = new int[]{4,5,1,9,9,1,2,3,12};
int[] top7 = topK(number,7);
for(int i=0;i<top7.length;i++){
System.out.print(top7[i]+" ");
}

}
private static int[] topK(int[] number,int k) {
int[] top7 = new int[k];
for (int i = 0; i < k; i++) {
top7[i] = number[i];
}
MinHeap minHeap = new MinHeap(top7);
for(int i = k;i<number.length;i++){
int root = minHeap.getRoot();
if(number[i]<=root){
break;
}else{
minHeap.setRoot(number[i]);
}
}