//為了測試運行內存調大一點
ini_set('memory_limit', '2024M');

//實現一個快速排序函數
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),0,10));
var_dump(time());

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

 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,0,10);

//獲取最后一個有子節(jié)點的索引位置
//因為在構造小頂堆的時候是從最后一個有左或右節(jié)點的位置
//開始從下往上不斷的進行移動構造（具體可看上面的圖去理解）
$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];
  /*
   重新調用生成小頂堆函數進行維護，只不過這次是從堆頂
   的索引位置開始自上往下進行維護，因為我們只是把堆頂
   的元素給替換掉了而其余的還是按照根節(jié)點小于左右節(jié)點
   的順序擺放這也就是我們上面說的，只是相對調整下，并
   不是全部調整一遍
  */
  Heap($topArr,0);
 }
}
var_dump(time());