힙은 우선순위 큐를 구현하기 위해 설계된 데이터 구조로 바이너리 힙(바이너리 트리의 일종)을 구성하여 구현됩니다. 가장 큰 루트 노드가 있는 힙을 최대 힙 또는 큰 루트 힙이라고 하며, 가장 작은 루트 노드가 있는 힙을 최소 힙 또는 작은 루트 힙이라고 합니다. 이진 힙은 정렬(힙 정렬)에도 일반적으로 사용됩니다. 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 )
고급 계산기 기능의 PHP 스택 기반 구현에 대한 자세한 설명
위 내용은 PHP의 SplHeap 힙에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!