欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP之SplHeap堆详解

程序员文章站 2022-04-30 20:29:45
...
堆(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堆排序实现代码

JavaScript中的堆排序详解

PHP基于堆栈实现高级计算器功能详解

以上就是PHP之SplHeap堆详解的详细内容,更多请关注其它相关文章!