PHP二叉堆是什么

　　堆可以視為一棵完全的二叉樹,完全二叉樹的一個“優(yōu)秀”的性質(zhì)是,除了最底層之外,每一層都是滿的,這使得堆可以利用數(shù)組來表示,每一個結(jié)點對應(yīng)數(shù)組中的一個元素.大家知道PHP二叉堆是什么嗎?下面就跟隨小編一起來看看吧!

　　在以往工作或者面試的時候常會碰到一個問題，如何實現(xiàn)海量TopN，就是在一個非常大的結(jié)果集里面快速找到最大的前10或前100個數(shù)，同時要保證內(nèi)存和速度的效率，我們可能第一個想法就是利用排序，然后截取前10或前100，而排序?qū)τ诹坎皇翘貏e大的時候沒有任何問題，但只要量特別大是根本不可能完成這個任務(wù)的，比如在一個數(shù)組或者文本文件里有幾億個數(shù)，這樣是根本無法全部讀入內(nèi)存的，所以利用排序解決這個問題并不是最好的，所以我們這里就用php去實現(xiàn)一個小頂堆來解決這個問題.

　　二叉堆

　　二叉堆是一種特殊的堆，二叉堆是完全二叉樹或者是近似完全二叉樹，二叉堆有兩種，最大堆 和 最小堆，最大堆：父結(jié)點的鍵值總是大于或等于任何一個子節(jié)點的鍵值;最小堆：父結(jié)點的鍵值總是小于或等于任何一個子節(jié)點的鍵值

　　小頂堆-(圖片來自網(wǎng)絡(luò))

　　二叉堆一般用數(shù)組來表示(看上圖)，例如，根節(jié)點在數(shù)組中的位置是0，第n個位置的子節(jié)點分別在2n+1和 2n+2，因此，第0個位置的子節(jié)點在1和2，1的子節(jié)點在3和4，以此類推，這種存儲方式便于尋找父節(jié)點和子節(jié)點。

　　具體概念問題這里就不在多說了，如果對二叉堆有疑問的可以在好好了解下這個數(shù)據(jù)結(jié)構(gòu)，下面我們就針對上述topN問題來用php代碼實現(xiàn)并解決，為了看出區(qū)別這里先用排序的方式去實現(xiàn)下看下效果如何。

　　利用快速排序算法來實現(xiàn) TopN

　　//為了測試運行內(nèi)存調(diào)大一點ini_set('memory_limit', '2024M');//實現(xiàn)一個快速排序函數(shù)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++){> $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); }//構(gòu)造500w不重復(fù)數(shù)for($i=0;$i<5000000;$i++){ $numArr[] = $i; }//打亂它們shuffle($numArr);//現(xiàn)在我們從里面找到top10最大的數(shù)var_dump(time());print_r(array_slice(quick_sort($all),0,10));var_dump(time());

　　運行之后結(jié)果

　　可以看到上面打印出了top10的結(jié)果，并輸出了下運行時間，大概99s左右，但這只是500w個數(shù)且全部能裝入內(nèi)存的情況，如果我們有一個文件里面有5kw或5億個數(shù)，肯定就會有些問題了.

　　利用二叉堆算法來實現(xiàn) TopN

　　實現(xiàn)流程是：

　　1、先讀取10個或100個數(shù)到數(shù)組里面，這就是我們的topN數(shù).

　　2、調(diào)用生成小頂堆函數(shù)，把這個數(shù)組生成一個小頂堆結(jié)構(gòu)，這個時候堆頂一定是最小的.

　　3、從文件或者數(shù)組依次遍歷剩余的所有數(shù).

　　4、每遍歷出來一個則跟堆頂?shù)脑�素進行大小比較，如果小于堆頂元素則拋棄，如果大于堆頂元素則替換之.

　　5、跟堆頂元素替換完畢之后，在調(diào)用生成小頂堆函數(shù)繼續(xù)生成小頂堆，因為需要再找出來一個最小的.

　　6、重復(fù)以上4~5步驟，這樣當(dāng)全部遍歷完畢之后，我們這個小頂堆里面的就是最大的topN，因為我們的小頂堆永遠都是排除最小的留下最大的，而且這個調(diào)整小頂堆速度也很快，只是相對調(diào)整下，只要保證根節(jié)點小于左右節(jié)點就可以.

　　7、算法復(fù)雜度的話按top10最壞的情況下，就是每遍歷一個數(shù)，如果跟堆頂進行替換，需要調(diào)整10次的情況，也要比排序速度快，而且也不是把所有的內(nèi)容全部讀入內(nèi)存，可以理解成就是一次線性遍歷.

　　//生成小頂堆函數(shù)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); }}//這里為了保證跟上面一致，也構(gòu)造500w不重復(fù)數(shù)/* 當(dāng)然這個數(shù)據(jù)集并不一定全放在內(nèi)存，也可以在 文件里面，因為我們并不是全部加載到內(nèi)存去進 行排序*/for($i=0;$i<5000000;$i++){ toparr="array_slice($numArr,0,10);//獲取最后一個有子節(jié)點的索引位置//因為在構(gòu)造小頂堆的時候是從最后一個有左或右節(jié)點的位置//開始從下往上不斷的進行移動構(gòu)造(具體可看上面的圖去理解)$idx" -="" 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]; /* 重新調(diào)用生成小頂堆函數(shù)進行維護，只不過這次是從堆頂 的索引位置開始自上往下進行維護，因為我們只是把堆頂 的元素給替換掉了而其余的還是按照根節(jié)點小于左右節(jié)點 的順序擺放這也就是我們上面說的，只是相對調(diào)整下，并 不是全部調(diào)整一遍 */ Heap($topArr,0); }}var_dump(time());

　　運行之后結(jié)果

　　可以看到最終的結(jié)果也是top10，只不過時間只用了1s左右，而且無論是內(nèi)存還是時間效率都滿足我們的要求，而且跟排序比最好的一點就是不用把所有的數(shù)據(jù)集都讀如到內(nèi)存里面來，因為我們不需要排序，而上面是為了演示，所以直接在內(nèi)存構(gòu)造了500w元素，然而我們可以把這個全部轉(zhuǎn)移到文件里面去，然后一行一行讀取進行比較，因為我們這個數(shù)據(jù)結(jié)構(gòu)的核心點就是線性遍歷跟內(nèi)存里面很小的小頂堆結(jié)構(gòu)進行比較，最終得到TopN.

【PHP二叉堆是什么】相關(guān)文章：

php如何實現(xiàn)的二叉樹遍歷(示例)10-17

php是什么11-13

PHP的變量是什么06-10

PHP簡介是什么09-04

PHP隊列是什么10-29

php語言是什么05-21

php是什么格式07-24

php是什么文件10-09

PHP框架是什么09-23