Detaillierte Erklärung des SplHeap-Heaps von PHP

Heap ist eine Datenstruktur zur Implementierung von Prioritätswarteschlangen. Sie wird durch den Aufbau eines binären Heaps (eine Art Binärbaum) implementiert. Der Heap mit dem größten Wurzelknoten wird als maximaler Heap oder großer Root-Heap bezeichnet, und der Heap mit dem kleinsten Wurzelknoten wird als minimaler Heap oder kleiner Root-Heap bezeichnet. Binäre Heaps werden auch häufig zum Sortieren (Heap-Sortierung) verwendet. SplHeap ist eine abstrakte Klasse, die die Schnittstellen Iterator und Countable implementiert. Der maximale Heap (SplMaxHeap) und der minimale Heap (SplMinHeap) werden durch Vererbung implementiert und können direkt in PHP-Programmen verwendet werden.

Klassenzusammenfassung:

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 )
}

Beispielbeschreibung:

<?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();
}
?>

Die obige Ausgabe:

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

Verwandte Empfehlungen:

PHP-Heap-Sort-Implementierungscode

Detaillierte Erläuterung der Heap-Sortierung in JavaScript

Detaillierte Erläuterung der erweiterten Rechnerfunktion, die von PHP basierend auf dem Stack implementiert wird

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung des SplHeap-Heaps von PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!