1亿个数找到1000个最大值 JavaScript利用堆排序实现 topN topK问题

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;         //Top10
var LEN = 20; //1亿个整数
var arrs = []; // 装1亿整数的数组
var arr = [] ; // 装十个整数的数组
//数组长度
var len = 8;
//堆中元素的有效元素 heapSize<=len
var 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);
    }
}