//实现一个快速排序函数
function quick_sort(array $array){
$length = count($array);
$left_array = array();
$right_array = array();
if($length <= 1){
return $array;
}
$key = $array[0];
for($i=1;$i<$length;$i++){
if($array[$i] > $key){
$right_array[] = $array[$i];
}else{
$left_array[] = $array[$i];
}
}
$left_array = quick_sort($left_array);
$right_array = quick_sort($right_array);
return array_merge($right_array,array($key),$left_array);
}

//构造500w不重复数
for($i=0;$i<5000000;$i++){
$numArr[] = $i;
}
//打乱它们
shuffle($numArr);

//现在我们从里面找到top10最大的数
var_dump(time());
print_r(array_slice(quick_sort($all),10));
var_dump(time());

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

if($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不重复数
/
当然这个数据集并不一定全放在内存，也可以在
文件里面，因为我们并不是全部加载到内存去进
行排序
/
for($i=0;$i<5000000;$i++){
$numArr[] = $i;
}
//打乱它们
shuffle($numArr);

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

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

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

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