# 堆（Heap） [TOC] 在服務器程序開發中經常要用到排序功能，如會員積分榜。普通的`array`數據結構，使用`sort`進行排序，即使使用了最快的快速排序方法，實際上也會存在較大的計算開銷。因此在內存中維護一個有序的內存結構可以有效低避免`sort`排序的計算開銷。 在`PHP`中`SplHeap`就是一種有序的數據結構。數據總是按照最小在前或最大在前排序。新插入的數據會自動進行排序。 ## 定義 `SplHeap`數據結構需要指定一個`compare`方法來進行元素的對比，從而實現自動排序。`SplHeap`類本身是`abstract`的，不能直接`new`。 需要編寫一個子類，并實現`compare`方法。 ~~~ //最大堆 class MaxHeap extends SplHeap { protected function compare($a, $b) { return $a - $b; } } //最小堆 class MinHeap extends SplHeap { protected function compare($a, $b) { return $b - $a; } } ~~~ ## 使用 定義好子類后，可使用`insert`方法插入元素，插入的元素會使用`compare`方法與已有元素進行對比，自動排序。 ~~~ $list = new MaxHeap; $list->insert(56); $list->insert(22); $list->insert(35); $list->insert(11); $list->insert(88); $list->insert(36); $list->insert(97); $list->insert(98); $list->insert(26); ~~~ * `SplHeap`底層使用跳表數據結構，`insert`操作的時間復雜度為`O(Log(n))` 注意這里只能插入數字，因為我們定義的`compare`不支持非數字對比。如果要支持插入數組或對象，可重新實現`compare`方法。 ~~~ class MyHeap extends SplHeap { protected function compare($a, $b) { return $a->value - $b->value; } } class MyObject { public $value; function __construct($value) { $this->value = $value; } } $list = new MyHeap; $list->insert(new MyObject(56)); $list->insert(new MyObject(12)); ~~~ 使用`foreach`遍歷堆，可以發現是有序輸出。 ~~~ foreach($list as $li) { echo $li."\n"; } ~~~