PHP의 SplHeap 힙에 대한 자세한 설명

힙은 우선순위 큐를 구현하기 위해 설계된 데이터 구조로 바이너리 힙(바이너리 트리의 일종)을 구성하여 구현됩니다. 가장 큰 루트 노드가 있는 힙을 최대 힙 또는 큰 루트 힙이라고 하며, 가장 작은 루트 노드가 있는 힙을 최소 힙 또는 작은 루트 힙이라고 합니다. 이진 힙은 정렬(힙 정렬)에도 일반적으로 사용됩니다. 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 (&#39;a&#39; => 12));
$heap->insert(array (&#39;b&#39; => 20));
$heap->insert(array (&#39;c&#39; => 23));
$heap->insert(array (&#39;d&#39; => 32));
$heap->insert(array (&#39;e&#39; => 15));
$heap->insert(array (&#39;f&#39; => 17));
$heap->insert(array (&#39;g&#39; => 31));
$heap->insert(array (&#39;h&#39; => 11));
$heap->insert(array (&#39;i&#39; => 18));
$heap->insert(array (&#39;j&#39; => 24));

var_dump($heap->top());

while ($heap->valid()) {
    $cur = $heap->current();
    list ($team, $score) = each($cur);
    echo $team . &#39;: &#39; . $score . &#39;<br/>&#39;;
    $heap->next();
}
?>

위 출력:

array (size=1)
'd' => int 32
d: 32
g: 31
j: 24
c )


고급 계산기 기능의 PHP 스택 기반 구현에 대한 자세한 설명

위 내용은 PHP의 SplHeap 힙에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!