1亿个数找到1000个最大值 JavaScript实现 topN topK问题
1亿个数找到1000个最大值其实就是找1亿个数中前1000大的数，首先以一亿个数字中的前1000个数建立小顶堆
这样我们可以保证这前一千个数字的堆顶是最小的（因为小顶堆的的堆顶是小于它的左右孩子的）这样我们依次比较1000之后的数字一直到第1亿个数，例如：第1001个数和小顶堆的堆顶比较，如果比堆顶小的话那么它一定比1000个数这里面的任意的数都小，所以不可能是前1000大的数，如果第1001个数比小顶堆的堆顶大的话，那么这个堆顶就一定不是前1000大的数，所以此时这个第1001的数代替这个堆顶，代替堆顶之后此时的小顶堆已经不一定是小顶堆了所以我们需要进行堆调整，来使其变成小顶堆。 堆调整的过程其实就是依照小顶堆的特点（堆顶比左右孩子小），如果堆顶大于左右孩子就将其与对应孩子交换，交换后左右孩子再和它的左右孩子进行比较。一直进行到不比左右孩子大为止。
对应JavaScript代码如下：（在此将1亿改成20，将1000改成8，20个数中找到8个最大值）
var N = 8; //Top10var LEN = 20; //1亿个整数var arrs = []; // 装1亿整数的数组var arr = [] ; // 装十个整数的数组//数组长度var len = 8;//堆中元素的有效元素 heapSize<=lenvar heapSize = len;//生成随机数组for (let i = 0; i < LEN; i++) { arrs[i] = Math.floor(Math.random() * 50);}console.log(arrs)//构建初始堆for (let i = 0; i < N; i++) { arr[i] = arrs[i];}// 初次建立size = 10的小顶堆以这十亿个整数中前10个数console.log(arr)//构建小顶堆buildMinHeap(); // 将这前十个数每个非叶子结点 堆调整建立小顶堆// 此时arr是以前十个arrs组成的小跟堆for (let i = N; i < LEN; i++) { // 此时模拟数据流 从第11个到第一亿个数分别进入 和小跟堆的堆顶比 比堆顶小的话就被淘汰，比堆顶大的话将其和堆顶交换，进行堆调整 if (arrs[i] > arr[0]) { arr[0] = arrs[i]; minHeap(0); }}console.log('一亿里面前十个元素', arr)/** * 建小顶堆 */function buildMinHeap () { let size = len / 2 - 1; for (let i = size; i >= 0; i--) { minHeap(i); } console.log('初小跟堆', arr)}/** * i节点为根及子树是一个小堆 * @param i */// 堆调整的筛选function minHeap (i) { var l = 2 * i + 1; // 左孩子 var r = 2 * i + 2; // 右孩子 var t // 存交换的暂时参数 var index = i; // index 存最小坐标 if (l < heapSize && arr[l] < arr[index]) { index = l; } if (r < heapSize && arr[r] < arr[index]) { index = r; } if (index != i) { t = arr[index]; arr[index] = arr[i]; arr[i] = t; //继续堆调整 minHeap(index); }}
