初始化最小堆代码如下

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 并被添加「」标签，已有 640 位童鞋阅读过。