SplHeap（堆） · PHP笔记

# [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 | ![](https://i.vgy.me/n7RdzD.png) ``` 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'@@@@@ '; 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'@@@@@ '; echo $splHeap->isCorrupted();// echo $splHeap->isEmpty();// echo'@@@@@ '; 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'@@@@@ '; echo $splHeap->rewind(); echo $splHeap->top();//33 echo'@@@@@ '; foreach ($splHeap as $item) { echo ' '.$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 .' '. 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 ```