堆(Heap)就是為了實現優先權佇列而設計的一種資料結構,它是透過建構二元堆(二元樹的一種)來實現。根節點最大的堆叫做最大堆或大根堆,根節點最小的堆叫做最小堆或小根堆。二元堆也常用於排序(堆排序)。 SplHeap 是一個抽象類,實作了Iterator , Countable介面。最大堆(SplMaxHeap)和最小堆(SplMinHeap)就是繼承它實現的,可以在PHP程式中直接使用。
類別摘要:
abstract SplHeap implements Iterator , Countable { // 创建一个空堆 public __construct ( void ) // 比较两个节点的大小 abstract protected int compare ( mixed $value1 , mixed $value2 ) // 返回堆节点数 public int count ( void ) // 返回迭代指针指向的节点 public mixed current ( void ) // 从堆顶部提取一个节点并重建堆 public mixed extract ( void ) // 向堆中添加一个节点并重建堆 public void insert ( mixed $value ) // 判断是否为空堆 public bool isEmpty ( void ) // 返回迭代指针指向的节点的键 public mixed key ( void ) // 迭代指针指向下一节点 public void next ( void ) // 恢复堆 public void recoverFromCorruption ( void ) // 重置迭代指针 public void rewind ( void ) // 返回堆的顶部节点 public mixed top ( void ) // 判断迭代指针指向的节点是否存在 public bool valid ( void ) }
範例說明:
<?php /** * 实现一个自己的最大堆 * * @author 疯狂老司机 */ class iMaxHeap extends SplHeap { /** * 实现compare抽象方法,使用关联数组的值进行比较排序 * SplMaxHeap不能满足我们的需求 */ 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; } } $heap = new iMaxHeap(); $heap->insert(array ('a' => 12)); $heap->insert(array ('b' => 20)); $heap->insert(array ('c' => 23)); $heap->insert(array ('d' => 32)); $heap->insert(array ('e' => 15)); $heap->insert(array ('f' => 17)); $heap->insert(array ('g' => 31)); $heap->insert(array ('h' => 11)); $heap->insert(array ('i' => 18)); $heap->insert(array ('j' => 24)); var_dump($heap->top()); while ($heap->valid()) { $cur = $heap->current(); list ($team, $score) = each($cur); echo $team . ': ' . $score . '<br/>'; $heap->next(); } ?>
以上輸出:
array (size=1)
'd' => int 32
d: 32
g: 31
j: 24
c: 23
b: 20
i: 18
f: 17
e: 15
a: 12
h: 11
相關推薦:
#以上是PHP之SplHeap堆詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!