Explication détaillée du tas SplHeap de PHP

Heap est une structure de données conçue pour implémenter des files d'attente prioritaires. Elle est implémentée en construisant un tas binaire (un type d'arbre binaire). Le tas avec le plus grand nœud racine est appelé tas maximum ou grand tas racine, et le tas avec le plus petit nœud racine est appelé tas minimum ou petit tas racine. Les tas binaires sont également couramment utilisés pour le tri (tri par tas). SplHeap est une classe abstraite qui implémente les interfaces Iterator et Countable. Le tas maximum (SplMaxHeap) et le tas minimum (SplMinHeap) sont implémentés en héritant et peuvent être utilisés directement dans les programmes PHP.

Résumé du cours :

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

Exemple de description :

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

La sortie ci-dessus :

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

Recommandations associées :

Code d'implémentation du tri par tas PHP

Explication détaillée du tri de tas en JavaScript

Explication détaillée de la fonction de calculatrice avancée implémentée par PHP basée sur la pile

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!