数据结构之PHP(最大堆)实现优先队列

前面我们一起学习了数组, 栈, 队列, 链表, 二分搜索树. 今天我们来学习一下使用最大堆这种数据结构实现优先队列. 先了解一下什么是优先队列。

一、优先队列概念
听这个名字就能知道，优先队列也是一种队列。在普通队列遵循的原则是 先进先出；后进后出 原则。但是在优先队列中， 出队顺序和入队顺序无关，和优先级有关系。在有些情况下，可能需要找到元素集合中的最小或者最大元素，就可以使用优先队列来完成操作。
他支持插入和删除最小值操作（返回并删除最小元素）或删除最大值操作(返回并删除最大元素). 这些操作等同于 队列的 enQueue *和 *deQueue操作,区别在于，对于优先队列，元素进入队列的顺序可能与其被操作的顺序不同，作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

二、二叉堆

一、堆性质

二叉堆 是一种特殊的完全二叉树, 二叉堆也叫 堆()。

当 堆 中的所有节点大于等于它的子节点， 我们称这个堆为最大堆，相反，当堆中所有的节点小于等于它的子节点，我们称这个堆为最小堆。

(堆 的示意图)

二、堆实现本质

堆本质上是一个完全二叉树, 所以可以使用数组这样的数据结构进行标识,

若索引是从 i=0 开始的，这样对于下标为i 的结点 a[i]来说，其左孩子的下标为 left(i) = 2∗i+1，右孩子的下标为 2∗i+2。且不论 i 是奇数还是偶数，其父亲结点（如果有的话）就是 parent = (i - 1)/2 取整。

(下标从0开始 的示意图)

若索引是从 i=1 开始的，这样对于下标为i 的结点 a[i]来说，其左孩子的下标为 left(i) = 2∗i，右孩子的下标为 right(i) = 2∗i+1。且不论 i 是奇数还是偶数，其父亲结点（如果有的话）就是 parent(i) = **i/2 取整。**

(下标从1开始 的示意图)

三、优先队列最基本的操作

1、添加元素( sift up)

当有新的数据加入到优先队列的时, 新的数据首先被放在二叉堆的底部。不断的进行向上筛选的操作，即如果发现该数据的优先级别比父节点的优先级别还要高，那么就和父节点的元素进行相互交换，再接着继续往上进行比较，直到无法进行交换为止。

(添加一个元素52 的示意图)

2、取出元素( sift down)

当堆顶的元素被取出时,要更新堆顶的元素来作为下一次按照优先级顺序被取出的对象,需要将堆底部的元素放置到堆顶, 然后不断的对他执行往下筛选操作。
将该元素和他两个孩子节点比较优先级，如果优先级最高的是其中的一个孩子，就将该元素和那个孩子进行交换，然后反复进行下去，直到无法继续交换为止。

(取出最大元素 的示意图)
四、代码实现

MaxHeap.php

<?php
/**
 * Created by : PhpStorm
 * User: think abel
 * Date: 2021/1/18 0018
 * Time: 23:45
 */

include 'ArrayStructure/ArrayStructure.php';

class MaxHeap
{
    private $data;

    public function __construct(int $capacity)
    {
        $this->data = new ArrayStructure($capacity);
    }

    /**
     * Notes: 获取数量
     * User: think abel
     * Date: 2021/1/18 0018
     * Time: 23:47
     *
     * @return int
     */
    public function getSize(): int
    {
        return $this->data->getSize();
    }

    /**
     * Notes: 数组是否为空
     * User: think abel
     * Date: 2021/1/18 0018
     * Time: 23:48
     *
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->data->isEmpty();
    }

    /**
     * Notes: 返回完全二叉树的数组表示中, 一个索引所表示元素的父亲节点的索引
     * User: think abel
     * Date: 2021/1/18 0018
     * Time: 23:49
     *
     * @param int $index
     *
     * @return string
     */
    private function parent(int $index)
    {
        if ($index == 0) {
            return "index-0 doesn't have parent.";
        }

        return ($index - 1) / 2;
    }

    /**
     * Notes: 返回完全二叉树的数组表示中, 一个索引所表示元素的左孩子节点的索引
     * User: think abel
     * Date: 2021/1/18 0018
     * Time: 23:52
     *
     * @param int $index
     *
     * @return int
     */
    private function left(int $index): int
    {
        return ($index * 2) + 1;
    }

    /**
     * Notes: 返回完全二叉树的数组表示中, 一个索引所表示元素右孩子节点的索引
     * User: think abel
     * Date: 2021/1/18 0018
     * Time: 23:52
     *
     * @param int $index
     *
     * @return int
     */
    private function right(int $index): int
    {
        return ($index * 2) + 2;
    }

    /**
     * Notes: 往堆中添加元素
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:00
     *
     * * @param $val
     */
    public function add($val)
    {
        $this->data->addLast($val);
        $this->siftUp($this->data->getSize() - 1);
    }

    /**
     * Notes: 向堆中添加元素 (数据上浮)
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:11
     *
     * @param $key
     */
    private function siftUp($key)
    {
        // 传递的key 要大于 0 并且 传过来索引位置的元素 还要 小于添加的元素
        while ($key > 0 && $this->data->get($this->parent($key)) < $this->data->get($key)) {
            $this->data->swap($key, $this->parent($key));
            $key = $this->parent($key);
        }
    }

    /**
     * Notes: 往堆中移除元素
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:00
     *
     */
    public function remove()
    {
        $max = $this->findMax();
        // 把最大的元素和最后一位元素进行交换
        $this->data->swap(0, $this->data->getSize() - 1);
        $this->data->removeLast();

        $this->siftDown(0);
        return $max;
    }

    /**
     * Notes: 往堆中移除元素  (数据下沉)
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:15
     *
     * @param $key
     */
    public function siftDown($key)
    {
        while ($this->left($key) < $this->data->getSize()) {
            $leftChild = $this->left($key);

            // 如果右子树索引 小于 当前 数组大小 (说明有右子树)
            // 并且 当前右子树索引位置上的值 大于 左子树索引位置上的值
            if (
                $leftChild + 1 < $this->data->getSize()
                && $this->data->get($leftChild + 1) > $this->data->get($leftChild)
            ) {
                $leftChild = $this->right($key);
            }

            // 此时 $this->data[$leftChild] 是 leftChild 和 rightChild 中 最大的值
            if ($this->data->get($key) >= $this->data->get($leftChild)) {
                break;
            }

            $this->data->swap($key, $leftChild);
            $key = $leftChild;
        }

    }

    /**
     * Notes: 发现元素中最大元素
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:18
     */
    public function findMax()
    {
        if (!$this->data->getSize()) {
            return "Can not findMax when heap is empty";
        }

        return $this->data->getFirst();
    }
}

ArrayStructure.php

<?php

class ArrayStructure
{
    // 数组实际元素
    private $size = 0;

    // 数组的容量大小
    private $capacity = 0;

    // 用于存放数据
    private $data = [];

    /**
     * ArrayStruct constructor.
     *
     * @param int $capacity 数组容量大小
     */
    public function __construct($capacity = 10)
    {
        $this->capacity = $capacity;
    }

    /**
     * Notes: 获取数组实际元素个数
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:12
     *
     * @return int
     */
    public function getSize(): int
    {
        return $this->size;

    }

    /**
     * Notes: 扩容
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 17:08
     *
     * @param $factor
     */
    protected function resize($factor)
    {
        $this->capacity = $factor * $this->capacity;

    }

    /**
     * Notes: 获取数组的容量
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:14
     *
     * @return int
     */
    public function getCapacity(): int
    {
        return $this->capacity;

    }

    /**
     * Notes: 数组是否为空
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:16
     *
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size === 0;

    }

    /**
     * Notes: 往数组指定位置插入数据
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:27
     *
     * @param int $index 需要插入的下标/索引
     * @param int $ele   需要插入的元素
     */
    public function add(int $index, $ele): void
    {
        // 如果当前的实际大小 等于 当前容量, 则不可以进行插入
        try {
            if ($this->size === $this->capacity) {
                throw new Exception("添加失败, Array 已经到达最大容量");
            }

            if ($index < 0 || $index > $this->size) {
                throw new Exception("添加失败, index require >= 0 and <= " . $this->size);
            }

            /**
             * 从最后一个元素开始进行遍历, 直到下标 为 当前输入的 下标, 终止
             * 每次将当前遍历的数值 往后 移动一位
             */
            for ($i = $this->size - 1; $i >= $index; $i --) {
                $this->data[$i + 1] = $this->data[$i];
            }

            // 目前当前下标还是存在之前的元素, 因为当前元素已经移动到后面一位, 所以直接覆盖就好
            $this->data[$index] = $ele;

            // 维护当前实际大小
            $this->size ++;
        }
        catch (Exception $e) {
            echo $e->getMessage();
        }

    }

    /**
     * Notes: 向所有元素后添加一个元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:19
     */
    public function addLast($element): void
    {
        $this->add($this->size, $element);

    }

    /**
     * Notes: 向第一位添加一个元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:19
     */
    public function addFirst(int $element): void
    {
        $this->add(0, $element);

    }

    /**
     * Notes: 数组转字符串
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 15:50
     *
     * @return string
     */
    public function toString(): string
    {
        $str = 'Array: size = ' . $this->size . ',' . 'capacity = ' . $this->capacity . PHP_EOL;
        $str .= '[';
        for ($i = 0; $i < $this->size; $i ++) {
            $str .= $this->data[$i];
            if ($i != $this->size - 1) {
                $str .= ',';
            }
        }

        $str .= ']';
        return $str . PHP_EOL;

    }

    /**
     * Notes: 获取指定下标位置的元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:13
     *
     * @param int $index
     *
     * @return int
     */
    public function get($index)
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("获取失败, index require >= 0 and < " . $this->size);
            }

            return $this->data[$index];
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 获取最后一个
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 15:48
     *
     * @return int
     */
    public function getLast()
    {
        return $this->get($this->size - 1);
    }

    /**
     * Notes: 获取第一个
     * User: think abel
     * Date: 2021/1/10 0010
     * Time: 15:48
     *
     * @return int
     */
    public function getFirst()
    {
        return $this->get(0);
    }

    /**
     * Notes: 修改指定下标位置的元素为 ele
     * User: think abel
     * Date: 2021/1/9 0009
     * Time: 12:04
     *
     * @param int $index
     * @param int $ele
     *
     * @return string
     */
    public function set(int $index, int $ele)
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("获取失败, index require >= 0 and < " . $this->size);
            }

            $this->data[$index] = $ele;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除指定位置上的元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:19
     *
     * @param int $index
     *
     * @return int|string
     */
    public function remove(int $index): int
    {
        try {
            if ($index < 0 || $index >= $this->size) {
                throw new Exception("移除失败, index require >= 0 and < " . $this->size);
            }

            $return = $this->data[$index];

            for ($i = $index + 1; $i < $this->size; $i ++) {
                $this->data[$i - 1] = $this->data[$i];
            }

            $this->size --;
            return $return;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除第一个
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:39
     *
     * @return int
     */
    public function removeFirst(): int
    {
        try {
            return $this->remove(0);
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 删除最后一个
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:39
     *
     * @return int
     */
    public function removeLast()
    {
        try {
            return $this->remove($this->size - 1);
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }

    /**
     * Notes: 如果有元素, 就删除
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:44
     *
     * @param int $ele
     *
     * @return bool
     */
    public function removeElement(int $ele): bool
    {
        $index = $this->find($ele);
        if ($index != - 1) {
            $this->remove($index);
        }

    }

    /**
     * Notes: 是否包含元素
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:22
     *
     * @param int $ele
     *
     * @return bool
     */
    public function contains(int $ele): bool
    {
        for ($i = 0; $i < $this->size; $i ++) {
            if ($this->data[$i] == $ele) {
                return true;
            }
        }

        return false;

    }

    /**
     * Notes: 获取当前元素的索引
     * Author: PhpStorm
     * Date: 2021/1/8 0008
     * Time: 16:22
     *
     * @param int $ele
     *
     * @return int
     */
    public function find(int $ele): int
    {
        for ($i = 0; $i < $this->size; $i ++) {
            if ($this->data[$i] == $ele) {
                return $i;
            }
        }

        return - 1;

    }

    /**
     * Notes: 交换元素位置
     * User: think abel
     * Date: 2021/1/19 0019
     * Time: 0:06
     *
     * @param int $i
     * @param int $j
     *
     * @return string
     */
    public function swap(int $i, int $j)
    {
        try {
            if ($i < 0 || $i >= $this->size || $j < 0 || $j >= $this->size) {
                throw new Exception("Index is illegal.");
            }

            $t = $this->data[$i];
            $this->data[$i] = $this->data[$j];
            $this->data[$j] = $t;
        }
        catch (Exception $e) {
            return $e->getMessage();
        }

    }
}

五、优先队列复杂度对比

功能
入队 出队(取最大元素)
普通线性结构（数组、链表）
O(1)
O(n)（遍历所有元素）
顺序线性结构

O(N)
O(1)
堆
O(log n)
O(log n)

六、应用场景

    从一堆杂乱无章的数据当中按照一定的顺序(或者优先级)逐步地筛选岀部分乃至全部的数据。

举例:

    任意一个数组,找出前k大的数。

    解法1:

        先对这个数组进行排序,然后依次输出前k大的数,复杂度将会是 o(nlogn),其中,n是数组的元素个数。这是一种直接的办法

    解法2:

        使用优先队列,复杂度优化成O(logn)

        当数据量很大(即n很大),而k相对较小的时候,显然,利用优先队列能有效地降低算法复杂度, 因为要找出前k大的数,并不需要对所有的数进行排序

有错误的地方, 欢迎指正! 祝大家生活愉快~~

本作品采用《CC 协议》，转载必须注明作者和本文链接