堆(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中文网其他相关文章!