# 第 2 节优先队列的实现

# 优先队列的几种实现方式

可以很容易地想到「优先队列」有两种实现方式：「无序数组」和「有序数组」。

# 实现一：无序数组

入队：放入的时候，直接放在数组的末尾，时间复杂度：；
出队：每次拿出元素之前，我们都执行一次排序，或者像「选择排序」那样，把最大的那个拿出去（其他操作不赘述），时间复杂度是：，这里是数组的长度。

# 实现二：有序数组

入队：每次放入元素的时候，我们都执行一次排序，类似于「插入排序」的内层循，保持数组的有序性，时间复杂度。
出队：把最大的那个拿出去（其他操作不赘述）。

下面这个结论很重要：

可以看出，讲「优先队列」设计成线性结构，出队或者入队的时候，其中有一个操作一定是的，也就是说「出队」或者「入队」其中一个操作一定是。

伟大的计算机科学家平衡了入队和出队这两个操作的时间复杂度，这种数据结构就是「堆」。也就是说，不管是「入队」还是「出队」，总有一个操作得把「优先队列」中的元素都看一遍。而「堆」就是这样一个数据结构，能把降到。

# 三种数据结构对于实现优先队列的时间复杂度的比较

实现优先队列的数据结构	入队操作	出队操作
普通数组
顺序数组
堆

说明：表示以为底的的对数，在时间复杂度的概念下，我们一般忽略底数。原因是换底公式，具体推导请见时间复杂度与空间复杂度 (opens new window)，在这个文档里面搜索「对数或者是含有对数乘法因子的项，对数底都看作」。

以在个元素中选出前个元素为例。使用「有序数组」或者「无序数组」，最差情况下时间复杂度是，使用「堆」可以将时间复杂度降到：。事实上，时间复杂度是与的差异巨大的。理解这个事实是我们掌握「堆」以及相关算法的基础，正是因为使用「堆」这种数据结构，提高了我们算法的执行效率，我们才有必要研究「堆」，使用「堆」。

综上所述，「堆」是实现「优先队列」的高效的数据结构。根据出队的元素是当前整个队中最大的那个元素或者是最小的那个元素，「堆」有「最小堆」和「最大堆」之分。

# 最大堆与最小堆

「优先队列」是一种常见的数据结构，有两种「优先队列」。

一种「优先队列」每次可以从中拿到人为定义下、当前优先级「最高」的元素，即「最大堆」「大顶堆」「大根堆」；
另一种「优先队列」每次可以从中拿到人为定义下、当前优先级「最低」的元素，即「最小堆」「小顶堆」「小根堆」。

如果没有特别说明，我们下文所指的「优先队列」都指「最大堆」「大顶堆」「大根堆」，而「最小堆」「小顶堆」「小根堆」的实现我们不累赘叙述了，原理与「最大堆」一样。

可以看到，「堆」的入队和出队的时间复杂度都是，因此我们可以猜测 组织「堆」的结构是一棵树。

「优先队列」「堆」「二叉堆」的关系

# 二叉堆 Binary Heap 的定义

形如下面形状的一个结构就是「最大堆」。

第 1 条：「最大堆」是一棵「完全二叉树」

完全二叉树：从形状上看，除了最后一层之外，其它层结点的数量达到最大值，并且最后一层的结点全部集中在左侧。

「完全二叉树」的特点是：可以使用一个数组保存「完全二叉树」，而不必引入离散的树形结构，因为在通常情况下，操作数组的下标，比操作结点和指针要方便一些。（这一点非常重要，请读者仔细体会）。这样既可以利用数组元素可以快速访问的特点，又让结点和结点之间形成了「父」与「子」的结构关系。

第 2 条：任意一个结点，如果它有孩子结点的话，孩子结点的值一定不会大于父亲结点的值

如果一个数组中的元素，有如上特点，我们称之为 堆有序。「堆有序」不是我们通常理解意义上的「升序」或者「降序」。如果把数组排成「完全二叉树」的样子，且满足第 2 条，这个数组就是「堆有序」。这里要注意的是，通常数组的 0 号下标不使用，从 1 号下标开始使用。这只是一种习惯，因为这么做父子结点的下标关系更「好看」一些，仅此而已。有些时候也会使用从号下标开始的堆，例如「堆排序」就是这样。

# 从下标为 1 开始的数组实现的二叉堆的性质

我们自己画一个二叉堆（如下图），把下标标注在二叉堆上。从上到下、从左到右，从 1 号下标开始标记，即下图结点的旁边黑色的数字，我们不难发现这些数字的排列形成的规律。

从 1 开始编号的下标的规律：

规律 1：一个结点的左结点的下标是这个结点的下标的 2 倍；
规律 2：一个结点的右结点的下标是这个结点的下标的 2 倍 + 1。

因此

要想找到父结点：，注意这里不能整除的时候需要向下取整；
要想找到两个子结点：，。

温馨提示：这个两条性质不用记，我们只要拿一张纸，画一个草图，就能够推出父结点和孩子结点下标之间的关系。

上面这张图用数组表示出来就是一个最大堆，它在我们的程序中是这样表示的：

下标号	0	1	2	3	4	5	6	7	8	9	10
元素值	`null`

在这里啰嗦一句，如果我们使用树结构来保存上面那张图的数据，我们要创建个结点，并且还要指明它们之间的引用关系，那样做显然就太复杂了。这里请读者再次体会使用数组来表示一个完全二叉树的好处。

下面给出了使用数组实现「最大堆」的一个基本结构。

Java 代码：

// 我们这个版本的实现中，0 号下标是不存数据的，这一点一定要注意
public class MaxHeap {

    private int[] data;
    // 当前堆中存储的元素的个数
    private int count;

    // 堆中能够存储的元素的最大数量（为简化问题，不考虑动态扩展）
    private int capacity;

    // 初始化最大堆
    public MaxHeap(int capacity) {
        // 初始化底层数组元素（ 0 号下标位置不存数据，这是为了使得通过父结点获得左右孩子有更好的表达式）
        data = new int[capacity + 1];
        count = 0;
    }

    // 返回堆中的元素个数
    public int size() {
        return count;
    }

    // 返回一个布尔值，返回堆中是否为空
    public boolean isEmpty() {
        return count == 0;
    }

}

Python 代码：

class MaxHeap:
    def __init__(self, capacity):
        # 我们这个版本的实现中，0 号索引是不存数据的，这一点一定要注意
        # 因为数组从索引 1 开始存放数值
        # 所以开辟 capacity + 1 这么多大小的空间
        self.data = [None for _ in range(capacity + 1)]
        # 当前堆中存储的元素的个数
        self.count = 0
        # 堆中能够存储的元素的最大数量（为简化问题，不考虑动态扩展）
        self.capacity = capacity

    def size(self):
        """
        返回最大堆中的元素的个数
        :return:
        """
        return self.count

    def is_empty(self):
        """
        返回最大堆中的元素是否为空
        :return:
        """
        return self.count == 0

接下来两节的内容，我们介绍在「优先队列」的「出队」和「入队」操作中，如何保持「最大堆」数组的 堆有序 的性质。

作者：liweiwei1419 链接：https://suanfa8.com/priority-queue/implement 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

← 第 1 节优先队列简介第 3 节最大堆的第 1 个重要操作：SiftUp →

# 第 2 节 优先队列的实现