php heap,PHP之SplHeap堆詳解

堆(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

class iMaxHeap extends SplHeap {

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 . '

$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