topk.php

<?php
/**
 * Created by PhpStorm.
 * User: chentao
 * Date: 2019/12/24
 * Time: 11:56 AM
 */


//生成小顶堆函数
function Heap(&$arr,$idx){
    $left  = ($idx << 1) + 1;
    $right = ($idx << 1) + 2;

    if (!isset($arr[$left])){
        return;
    }

    if(isset($arr[$right]) && $arr[$right] < $arr[$left]){
        $l = $right;
    }else{
        $l = $left;
    }

    if ($arr[$idx] > $arr[$l]){
        $tmp = $arr[$idx];
        $arr[$idx] = $arr[$l];
        $arr[$l] = $tmp;
        Heap($arr,$l);
    }
}

//这里为了保证跟上面一致，也构造500w不重复数
/*
  当然这个数据集并不一定全放在内存，也可以在
  文件里面，因为我们并不是全部加载到内存去进
  行排序
*/
ini_set('memory_limit', '1024M');

$numArr = range(0,5000000,1);
//打乱它们
shuffle($numArr);

//先取出10个到数组
$topArr = array_slice($numArr,0,10);

//获取最后一个有子节点的索引位置
//因为在构造小顶堆的时候是从最后一个有左或右节点的位置
//开始从下往上不断的进行移动构造（具体可看上面的图去理解）
$idx = floor(count($topArr) / 2) - 1;

//生成小顶堆
for($i=$idx;$i>=0;$i--){
    Heap($topArr,$i);
}

var_dump(microtime());
list($t1, $t2) = explode(' ', microtime());
$st = (float)sprintf('%.0f', floatval($t1) + floatval($t2)*1000);
//这里可以看到，就是开始遍历剩下的所有元素
for($i = count($topArr); $i < count($numArr); $i++){
    //每遍历一个则跟堆顶元素进行比较大小
    if ($numArr[$i] > $topArr[0]){
        //如果大于堆顶元素则替换
        $topArr[0] = $numArr[$i];
        /*
          重新调用生成小顶堆函数进行维护，只不过这次是从堆顶
          的索引位置开始自上往下进行维护，因为我们只是把堆顶
          的元素给替换掉了而其余的还是按照根节点小于左右节点
          的顺序摆放这也就是我们上面说的，只是相对调整下，并
          不是全部调整一遍
        */
        Heap($topArr,0);
    }
}
var_dump($topArr);
list($t1, $t2) = explode(' ', microtime());
$et = (float)sprintf('%.0f', floatval($t1) + floatval($t2)*1000);

echo $et - $st;