关于堆:SPL数据结构2Heap最大堆最小堆

堆是一种常见的数据结构。其底层就是一个用数组实现的二叉树。然而没有父指针和子指针。依据堆属性来进行排序。分为最小堆和最大堆。

• 最小堆：父节点的值比每个子节点的值都要小
• 最大堆：父节点的值比每一个子节点的值都要大

个别利用在以下场景：

• 疾速排序 (取最大值 最小值)
• 优先队列

最大堆 / 最小堆

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());
}

上一篇：双向链表, 堆栈, 队列