# 堆（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"; } ~~~