红黑树和堆

红黑树和堆

红黑树和堆

红黑树(Red-Black Tree)是每个节点都带有颜色属性的二叉排序(查找)树,具备以下特性:
节点是红色或黑色;
根节点是黑色的;
每个叶子节点都是黑色的空节点(NulL).最后一层为null的节点为叶子节点;
如果一个结点是红色,那么它的子节点是黑色
对每个结点,从该结点到其叶子结点(null节点)的所有路径上包含相同数目的黑结点。

undefined

由于红黑树的特性,可以确保即使在最差情况下,红黑树也是大致平衡的 .算法复杂度为O(logn)

什么是堆

堆是一种特殊的二叉树,具备以下特性:
堆是一个完全二叉树
每个节点的值都必须大于等于(或小于等于)其左右孩子节点的值

如果每个节点的值都大于等于左右孩子节点的值,这样的堆叫大顶堆;如果每个节点的值都小于等于左右孩子节点的值,这样的堆叫小顶堆。

undefined

上图中,左侧的堆是大顶堆,右侧的堆是小顶堆,我们还可以得出这个结论:对应大顶堆,堆顶一定是最大值;对于小顶堆,堆顶一定是最小值。
class Heap
{
private $a = [];
private $n;
private $count;

public function __construct($capacity = 10)
{
$this->n = $capacity;
$this->count = 0;
}

public function insert($data)
{
if ($this->count >= $this->n) {
return false;
}
$this->count++;
$this->a[$this->count] = $data;
$i = $this->count;
while (floor($i/2) > 0 && $this->a[floor($i/2)] < $this->a[$i]) {
$temp = $this->a[$i];
$this->a[$i] = $this->a[floor($i/2)];
$this->a[floor($i/2)] = $temp;
$i = $i / 2;
}
return true;
}

public function remove() {
if ($this->count == 0)
return false;
$removeData = $this->a[1];
$this->a[1] = $this->a[$this->count];
$this->count--;
$i = 1; // 堆顶元素
while (true) {
$maxPos = $i;
if ($i*2 <= $this->count && $this->a[$i*2] > $this->a[$i]) {
$maxPos = 2 * $i;
}
if ($i*2 + 1 <= $this->count && $this->a[$i*2+1] > $this->a[$maxPos]) {
$maxPos = 2 * $i + 1;
}
if ($maxPos == $i) {
break;
}
$temp = $this->a[$i];
$this->a[$i] = $this->a[$maxPos];
$this->a[$maxPos] = $temp;
$i = $maxPos;
}
return $removeData;
}

public function __toString()
{
return json_encode(array_values($this->a));
}
}


$heap = new Heap();
$data = range(1, 10);
shuffle($data);
foreach ($data as $num) {
if (!$heap->insert($num)) {
break;
}
}

$sortedData = [];
while ($removedData = $heap->remove()) {
$sortedData[] = $removedData;
}
var_dump($heap); //创建的堆
print_r($sortedData);//移出

复杂度分析

先看时间复杂度,对堆排序而言,分为两个阶段,一个是堆的构建,一个是堆顶元素的删除。对于 n 个节点的堆化而言,通过数组存储,对应的时间复杂度是 O(n),对于堆顶元素的删除而言,需要遍历 n 个节点,并且,每次删除后需要重新堆化,对应的平均时间复杂度是 O(nlogn)。

所以综合下来,堆排序的时间复杂度和快速排序、归并排序一样,是 O(nlogn)。

堆排序的过程中,涉及到不相邻元素的交换(删除堆顶元素的时候),所以不是稳定的排序算法。
在删除堆顶元素的时候,使用了额外的存储空间存放被删除的堆顶元素.