堆(Heap)就是為了實現優先隊列而設計的一種數據結構，它是通過構造二叉堆(二叉樹的一種)實現。根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。二叉堆還常用于排序(堆排序)。 ![1352265671_1438.jpg-27.3kB][1] ## 類摘要 ```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 ) } ``` 從上面可以看到由于類中包含一個`compare`的抽象方法，所以該類必須為抽象類（不可實例化，只能被繼承使用）； **最小堆和最大堆其實就是對`compare`該抽象方法的一個算法的兩種呈現；** 也可以自己寫一個類繼承SplHeap按自己的方式來做排序； ## Example ### 自定義排序堆 ```php class MySimpleHeap extends SplHeap { //compare()方法用來比較兩個元素的大小，決定他們在堆中的位置 public function compare( $value1, $value2 ) { return ($value2 - $value1); } } $obj = new MySimpleHeap(); $obj->insert( 4 ); $obj->insert( 8 ); $obj->insert( 1 ); $obj->insert( 0 ); echo $obj->top(); //8 foreach( $obj as $number ) { echo $number; echo PHP_EOL; } ``` ### 最大堆與最小堆 ```php $heap = new SplMaxHeap(); $heap->insert(100); $heap->insert(80); $heap->insert(88); $heap->insert(70); $heap->insert(810); $heap->insert(800); //最大堆，從大到小排序 $heap->rewind(); while($heap->valid()){ echo $heap->key(),'=>',$heap->current(),PHP_EOL; $heap->next(); } ``` [1]: http://static.zybuluo.com/a5635268/oupyds2yiv6mdhw8nmikvdty/1352265671_1438.jpg