堆是一种常见的数据结构。其底层就是一个用数组实现的二叉树。然而没有父指针和子指针。 依据堆属性来进行排序。分为最小堆和最大堆。
- 最小堆：父节点的值比每个子节点的值都要小
- 最大堆：父节点的值比每一个子节点的值都要大
个别利用在以下场景：
- 疾速排序(取最大值 最小值)
- 优先队列
最大堆/最小堆
spl中SplHeap抽象类实现了堆数据结构。SplMaxHeap和SplMinHeap继承自SplHeap，别离用来实现最大堆和最小堆。以下代码以最大堆为例做阐明，最小堆的时候和最大堆相似
// 最大堆$maxheap = new SplMaxHeap();// 插入节点并重建堆$maxheap->insert(12);$maxheap->insert(3);$maxheap->insert(222);$maxheap->insert(2);$maxheap->insert(312);$maxheap->insert(3);$maxheap->insert(13);$maxheap->insert(32);$maxheap->insert(3);$maxheap->insert(1);echo "最大推顶层元素：" . $maxheap->top() . PHP_EOL;// extract提取顶层元素// 取出节点并重建堆 echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "判断是否是空堆：" . PHP_EOL;var_dump($maxheap->isEmpty());// 当堆长度为0 的时候该堆为空堆echo "以后堆长度：" . $maxheap->count() . PHP_EOL;实现自定义推排序
很多时候，单纯的数字大小比拟不能满足咱们对于堆数据结构的要求。比方咱们要基简单数组实现堆排序。SplHeap 类提供了compare形象办法，只有咱们实现本人的compare办法，就能够对任意数据类型进行最小堆最大堆排序
class MmaxHead extends SplHeap{ /** * 假如推中为关联数组 保留学生信息 依据成绩排名 * ['name'=>'Bob',score=>99.2] * * @param mixed $value1 * @param mixed $value2 * * @return int */ protected function compare($value1, $value2) { if ($value1['score'] > $value2['score']) { return 1; } elseif ($value1['score'] < $value2['score']) { return -1; } else { return 0; } }}$myheap = new MmaxHead();$myheap->insert(['name' => "bob1", "score" => 65]);$myheap->insert(['name' => "bob2", "score" => 34.3]);$myheap->insert(['name' => "bob3", "score" => 99.3]);$myheap->insert(['name' => "bob4", "score" => 23.4]);$myheap->insert(['name' => "bob5", "score" => 55]);$myheap->insert(['name' => "bob6", "score" => 66]);echo "问题最高的是" . PHP_EOL;var_dump($myheap->top());echo "顺次排名：" . PHP_EOL;while (!$myheap->isEmpty()) { var_dump($myheap->extract());}上一篇：双向链表,堆栈,队列