海量数据找到最大的100个数据
程序员文章站
2022-03-13 12:26:47
...
前言:
海量数据指的是数据量非常大,亿级的数据。如果是 int 型数据,int型数组占4个字节的内存,1亿个int型数据就得占用近400M的内存,计算机性能差的话很难一次性读入然后排序。所以一般的靠排序来做这道题是很尴尬的。
这里用最小堆来解决,上篇讲了大顶堆的原理及大顶堆的排序,这里由于是找最大的100条数据,所以要用到小顶堆。
小顶堆的满足条件如下:
1.堆顶的元素最小
2. 左右子节点的值都大于父节点的值。
实现思路
1.用1亿条数据的前100个数据建立一个小顶堆,然后从第101条数据遍历到最后的1亿条,如果数值大于堆顶的数据,则替换堆顶的数据然后从新建立小顶堆;
实现代码如下:
public class HeapSort {
public void buildMinHeap(int[] A) {
for (int i = parent(A.length - 1); i >= 0; i--) {
minHeapify(A, i, A.length);
}
System.out.println(".............建小根堆...............");
for (int j = 0; j < A.length; j++) {
System.out.println("A[" + j + "] = " + A[j]);
}
}
private void minHeapify(int[] A, int i, int heapSize) {
int l = left(i);
int r = right(i);
int largest = i;
if (l <= heapSize - 1 && A[l] < A[i])
largest = l;
if (r <= heapSize - 1 && A[r] < A[largest])
largest = r;
if (largest != i) {
int temp = A[i];
// swap
A[i] = A[largest];
A[largest] = temp;
this.minHeapify(A, largest, heapSize);
}
}
/**
* 找到数组最大的n个数:先是建一个n个数的小根堆,然后遍历从n到数组的大小,如果遍历的值大于堆顶的元素则替换堆顶的值,然后从堆顶开始调整最小堆
*
* @param arr
* @param n
*/
public void findKLargestValue(int[] arr, int n) {
int[] tmp = new int[10];
for (int i = 0; i < n; i++) {
tmp[i] = arr[i];
}
System.out.println(Arrays.toString(arr));
buildMinHeap(tmp);
int tp = 0;
for (int j = n; j < arr.length; j++) {
if (arr[j] > tmp[0]) {
tp = tmp[0];
tmp[0] = arr[j];
arr[j] = tp;
}
minHeapify(tmp, 0, tmp.length);
}
System.out.println(Arrays.toString(tmp));
}
}
测试代码:
HeapSort heapSort = new HeapSort();
int [] B = {3, 7, 2, 11, 3, 4, 9, 2, 18, 0, 33, 109, 35, 555, 1, 6, 99, 22, 77, 5, 767, 444};
heapSort.findKLargestValue(B, 10);
如果不了解小顶堆的可以看我的这篇文章:
大顶堆的原及即实现
上一篇: Debian11系统安装
下一篇: php如何去掉数组重复的值?