# [SplHeap](https://www.php.net/manual/zh/class.splheap.php#class.splheap) ### [堆原理]([https://www.jianshu.com/p/6b526aa481b1](https://www.jianshu.com/p/6b526aa481b1)) >[info]堆(Heap)就是為了實現優先隊列而設計的一種數據結構，它是通過構造二叉堆(二叉樹的一種)實現。根節點最大的堆叫做最大堆或大根堆（SplMaxHeap），根節點最小的堆叫做最小堆或小根堆（SplMinHeap）。二叉堆還常用于排序(堆排序) extract 出隊更為友好，即始終返回優先級最高的元素，優先級相投時會以堆調整的特性返回數據 >[danger] 注意，因為是`堆`實現，所以`rewind`方法是一個`no-op`沒有什作用的操作，因為`頭指針`始終指向`堆頂`，即`current`始終等于`top`，不像`List`只是游走指針，出隊是會刪除堆元素的，`extract`\=`current + next`（current出隊，從堆中刪除） 節點與它的父節點和子節點在數組中的位置關系： 公式： ~~~ parent(index) = floor((index - 1)/2) left(index) = 2index + 1 right(index) = 2index + 2 ~~~ 如：`[ 10, 14, 25, 33, 81, 82, 99 ]` >[danger]元素個數為7 so下面索引<=6才有子節點 所以 33, 81, 82, 99 無子節點 | Node | `index` | Parent index | Left child | Right child | | --- | --- | --- | --- | --- | | 10 | 0 | \-1(不是有效索引so無父節點) | 1 | 2 | | 14 | 1 | 0 | 3 | 4 | | 25 | 2 | 0 | 5 | 6 | | 33 | 3 | 1 | 7 | 8 | | 81 | 4 | 1 | 9 | 10 | | 82 | 5 | 2 | 11 | 12 | | 99 | 6 | 2 | 13 | 14 |  ``` abstract SplHeap implements Iterator , Countable { /* 方法 */ public __construct ( void ) abstract protected compare ( mixed $value1 , mixed $value2 ) : int //比較元素，以便在篩選時將它們正確地放在堆中，如果value1大于value2則為正整數，如果相等則為0，否則為負整數 public count ( void ) : int //返回元素的個數 Countable? public current ( void ) : mixed //返回當前記錄節點索引的值 超出范圍返回空 Iterator public extract ( void ) : mixed //從堆頂部提取節點并進行篩選 public insert ( mixed $value ) : void //通過篩選將一個元素插入堆中 public isCorrupted ( void ) : bool //判斷堆是否處于損壞狀態 public isEmpty ( void ) : bool //檢查堆是否為空 public key ( void ) : mixed //返回當前節點索引 Iterator public next ( void ) : void //移動到下一個節點 Iterator public recoverFromCorruption ( void ) : void //從損壞的狀態恢復并允許堆上的進一步操作 public rewind ( void ) : void //將指針指向迭代開始處 Iterator public top ( void ) : mixed //返回堆頂部的節點 public valid ( void ) : bool //檢查堆是否還有節點 Iterator } ``` ## **例子：** ``` //堆 class CustomSplHeap extends SplHeap{ //compare()方法用來比較兩個元素的大小，絕對他們在堆中的位置 public function compare( $value1, $value2 ) { //return ( $value2 - $value1) return ( $value1 - $value2 ); } } $splHeap = new CustomSplHeap(); $splHeap->insert(10); $splHeap->insert(14); $splHeap->insert(25); $splHeap->insert(33); $splHeap->insert(81); $splHeap->insert(82); $splHeap->insert(99); print_r($splHeap); echo'@@@@@<br>'; echo $splHeap->key();//6 echo $splHeap->current();//99 echo $splHeap->count();//7 echo $splHeap->next(); echo $splHeap->key();//5 echo $splHeap->current();//82 //返回堆頂部的節點 echo $splHeap->top();//82 echo $splHeap->rewind(); echo $splHeap->count();//6 echo $splHeap->key();//5 echo $splHeap->current();//82 echo $splHeap->extract();//82 echo'@@@@@<br>'; echo $splHeap->isCorrupted();// echo $splHeap->isEmpty();// echo'@@@@@<br>'; echo $splHeap->key();//4 echo $splHeap->current();//81 echo $splHeap->next(); echo $splHeap->key();//3 echo $splHeap->current();//33 echo $splHeap->extract();//33 echo $splHeap->key();//2 echo $splHeap->current();//25 echo'@@@@@<br>'; echo $splHeap->rewind(); echo $splHeap->top();//33 echo'@@@@@<br>'; foreach ($splHeap as $item) { echo '<br>'.$item;//25 14 10 } ``` ``` <?php class JupilerLeague extends SplHeap { /** * We modify the abstract method compare so we can sort our * rankings using the values of a given array */ public function compare($array1, $array2) { $values1 = array_values($array1); $values2 = array_values($array2); if ($values1[0] === $values2[0]) return 0; return $values1[0] < $values2[0] ? -1 : 1; } } // Let's populate our heap here (data of 2009) $heap = new JupilerLeague(); $heap->insert(array ('AA Gent' => 15)); $heap->insert(array ('Anderlecht' => 20)); $heap->insert(array ('Cercle Brugge' => 11)); $heap->insert(array ('Charleroi' => 12)); $heap->insert(array ('Club Brugge' => 21)); $heap->insert(array ('G. Beerschot' => 15)); $heap->insert(array ('Kortrijk' => 10)); $heap->insert(array ('KV Mechelen' => 18)); $heap->insert(array ('Lokeren' => 10)); $heap->insert(array ('Moeskroen' => 7)); $heap->insert(array ('Racing Genk' => 11)); $heap->insert(array ('Roeselare' => 6)); $heap->insert(array ('Standard' => 20)); $heap->insert(array ('STVV' => 17)); $heap->insert(array ('Westerlo' => 10)); $heap->insert(array ('Zulte Waregem' => 15)); // For displaying the ranking we move up to the first node $heap->top(); // Then we iterate through each node for displaying the result while ($heap->valid()) { //var_dump($heap->current()); foreach ($heap->current() as $key => $value) { $team=$key; $score=$value; } echo $team . ': ' . $score .'<br>'. PHP_EOL; $heap->next(); } 結果： Club Brugge: 21 Anderlecht: 20 Standard: 20 KV Mechelen: 18 STVV: 17 Zulte Waregem: 15 AA Gent: 15 G. Beerschot: 15 Charleroi: 12 Racing Genk: 11 Cercle Brugge: 11 Kortrijk: 10 Lokeren: 10 Westerlo: 10 Moeskroen: 7 Roeselare: 6 ```