7.1. 数据结构（PHP实现） -- 优先队列的底层实现（堆）

码农天地 - 2020-11-11 19:44:56

---

1. 说明：是基于二叉树来实现2. 时间复杂度操作时间复杂度入队O(logn)出队O(logn)3. 插入结点的上浮操作（为了将最大值放在最顶部）（在代码siftUp方法中）

4. 弹出最大结点后对最小值的下沉操作（在代码siftDown方法中）

5. 代码

<?php
/**
 * content: 堆的实现
 * auth: 俞佳明
 * creat: 2020-11-09 
 */

namespace HeapBundle;


use ArrayBundle\BaseArray;

class TreeHeap
{
    /**
     * 数据
     * @var BaseArray
     */
    protected $data;

    public function __construct()
    {
        $this->data = new BaseArray();
    }

    /**
     * 获取父结点的索引
     * @param int $index
     * @return int
     * @throws \Exception
     */
    public function parentIndex(int $index): int
    {
        if ($index <= 0) {
            throw new \Exception('索引必须大于0！');
        }
        return ($index - 1) / 2;
    }

    /**
     * 获取左儿子的索引
     * @param int $index
     * @return int
     */
    public function leftChildIndex(int $index): int
    {
        return $index * 2 + 1;
    }

    /**
     * 获取右儿子的索引
     * @param int $index
     * @return int
     */
    public function rightChildIndex(int $index): int
    {
        return $index * 2 + 2;
    }

    /**
     * 获取最大的值
     * @return string|int|null
     */
    public function getMaxValue()
    {
        return $this->data->getSize() > 0 ? $this->data->getFirst() : null;
    }

    /**
     * 弹出堆中最大的元素
     * @return int|string|null
     * @throws \Exception
     */
    public function popMaxValue()
    {
        // 如果不存在堆，就直接返回
        $maxValue = $this->getMaxValue();
        if (is_null($maxValue)) return null;
        $this->data->swap(0, $this->data->getSize() - 1);
        $this->data->del($this->data->getSize() - 1);

        // 最小值下沉
        $this->siftDown(0);

        return $maxValue;
    }

    /**
     * 添加数据
     * @param $value
     * @throws \Exception
     */
    public function add($value)
    {
        // 往数组的末尾追加元素
        $this->data->addLast($value);
        // 获取最后一个索引 并做 上浮操作
        $this->siftUp($this->data->getSize() - 1);
    }

    /**
     * 上浮操作，将最大的值上浮到最顶部
     * @param int $index 当前的索引
     * @throws \Exception
     */
    protected function siftUp(int $index)
    {
        // 如果索引大于0 且 父结点的值比当前结点的值要来的小， 则进入循环
        while ($index > 0 && bccomp($this->data->get($this->parentIndex($index)), $this->data->get($index)) < 0) {
            // 交换数组的索引下标
            $this->data->swap($index, $this->parentIndex($index));
            // 将父节点的索引变为当前索引，继续循环
            $index = $this->parentIndex($index);
        }
    }

    /**
     * 下沉操作，将最小值下沉到最底部
     * @param int $index
     * @throws \Exception
     */
    protected function siftDown(int $index)
    {
        while ($this->leftChildIndex($index) < $this->data->getSize()) {
            // 获取儿子结点的索引
            $childIndex = $this->leftChildIndex($index);
            // 比较左儿子和右儿子结点的值，将最大值的结点索引赋值给儿子结点索引
            if (bccomp($this->data->get($this->rightChildIndex($index)), $this->data->get($childIndex)) > 0) {
                $childIndex = $this->data->get($this->rightChildIndex($index));
            }

            // 比较结点值与儿子结点的值，如果比儿子结点要大就不处理
            if (bccomp($this->data->get($index), $this->data->get($childIndex)) >= 0) {
                break;
            }

            // 结点与儿子结点做换位
            $this->data->swap($index, $childIndex);

            // 往下赋值
            $index = $childIndex;
        }
    }

    /**
     * 打印数据
     * @return void
     */
    public function varDump(): void
    {
        echo (string)$this->data. PHP_EOL;
    }
}

6. 示例

<?php
require_once __DIR__ . '/../../vendor/autoload.php';
$heap = new HeapBundleTreeHeap();
       1
for ($i = 0; $i < 10; $i++) {
    $heap->add($i);
}

for ($i = 0; $i < 10; $i++) {
    var_dump($heap->popMaxValue());
}

int(9)
int(8)
int(3)
int(1)
int(4)
int(0)
int(7)
int(6)
int(5)
int(2)

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。

更多关于php的阅读

Tags 标签

数据结构php二叉树堆

扩展阅读