php 把一个普通数组初始化为 堆 二叉堆 O(n) 最小堆
初始化最小堆代码如下
function min_heap($tree)
{
$maxIndex = count($tree) - 1;
$lastParentIndex = ceil($maxIndex / 2 - 1);
$focusIndex = $lastParentIndex;
// 关注点从最后一个父节点向上
while ($focusIndex >= 0) {
// 关注点逐渐向下比较
$parentIndex = $focusIndex;
while ($parentIndex <= $lastParentIndex) {
// 不加哨兵,则左子树为2n+1,右子树为2n+2
// 第一个元素未哨兵时候,左子树为2n,右子树为2n+1
$leftIndex = $parentIndex * 2 + 1;
$rightIndex = $parentIndex * 2 + 2;
// 根据完全二叉树性质,如果右子树超出不存在,则这个父节点中比较小的肯定是左子树
if ($rightIndex > $maxIndex) {
$smallIndex = $leftIndex;
} else {
$smallIndex = $tree[$leftIndex] < $tree[$rightIndex] ? $leftIndex : $rightIndex;
}
// 利用下沉节点的方式把当前子树,调整为堆
// 选出左右子树中较小的
// 如果子树比父节点还小则下沉父节点
if ($tree[$smallIndex] < $tree[$parentIndex]) {
$tmp = $tree[$parentIndex];
$tree[$parentIndex] = $tree[$smallIndex];
$tree[$smallIndex] = $tmp;
// 原来的子节点变为新的父节点继续向下比较
$parentIndex = $smallIndex;
} else {
// 子节点都不小于父节点则开始下一个关注点的操作
break;
}
}
$focusIndex -= 1;
}
return $tree;
}
$tree = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
$heap = min_heap($tree);
var_dump($heap);
最后更新于 2021-08-27 07:22:16 并被添加「」标签,已有 575 位童鞋阅读过。
此处评论已关闭