【算法日积月累】9-堆与优先队列

这部分我们介绍一种新的数据结构堆（Heap），“堆”是实现“优先队列”的一个高效的数据结构。首先，我们来认识“优先队列”。

优先队列（priority queue）

“优先队列”是从下面的这种场景中抽象出来的数据结构。

例：班级里要选一名同学代表全班参加程序编程竞赛，此时我们只会关心第 1 名是谁，第 1 名本人不想参赛了，或者说第 1 名因为其它因素不符合参考资格，我们才考虑第 2 名，但也是从剩下的那些同学中挑出第 1 名。即当前我们只关心当前“最优”的那个元素，第 2 名及其以后的同学都不考虑了。

“优先队列”相对于“普通队列”而言。“普通队列”的性质是“先进先出，后进后出”。“优先队列”由元素的优先级决定出队的顺序。

普通队列	优先队列
先进先出，后进后出。由进入队列的时间顺序决定。	出队顺序与入队顺序无关，只与队列中元素的优先级有关，优先级最高的元素最先出队。

优先队列的主要操作

“优先队列”是一种抽象的数据结构，有两种“优先队列”。一种“优先队列”每次可以从中拿到我们定义下优先级“最高”的元素，即“最大堆”、“大顶堆”、“大根堆”，另一种“优先队列”每次可以从中拿到我们定义下优先级“最低”的元素，即“最小堆”、“小顶堆”、“小根堆”。如果没有特别说明，我们下文所指的“优先队列”都是指每次可以拿到优先级“最高”元素的优先队列。

“优先队列”的主要操作有：

1、入队

2、出队：优先队列的一个重要特点是：出队的时候总是取出优先级最高的那个元素。

如果不考虑时间复杂度，“优先队列”可以有以下两种实现方式：“无序数组”和“有序数组”。

实现1：无序数组。放入的时候，直接放在数组的末尾，时间复杂度： $O(1)$ 。每次拿出元素之前，我们都排个序，或者像“选择排序”那样，把最大的那个拿出去就好了，时间复杂度是： $O(n)$ 。

实现2：有序数组。每次放入元素的时候，我们都排个序，像插入排序内层循环那样，保持数组的有序性，时间复杂度 $O(n)$ ，把最大的那个拿出去 $O(1)$ 。

伟大的计算机科学家平衡了入队和出队这两个操作的时间复杂度，这种数据结构就是堆。

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

实现优先队列的数据结构	入队操作	出队操作
普通数组	$O(1)$	$O(n)$
顺序数组	$O(n)$	$O(1)$
堆	$O(\log n)$	$O(\log n)$

说明： $\log n$ 表示以 $2$ 为底的 $n$ 的对数。

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

我们发现，不管是“入队”还是“出队”，总有一个操作得把“优先队列”中的元素都看一遍。而“堆”就是这样一个数据结构，能把 $O(n)$ 降到 $O(\log n)$ 。

综上所述，“堆”是实现“优先队列”的高效的数据结构。“堆”有“最小堆”和“最大堆”，和上面一样，如果没有特别说明，我们下文所指的“堆”都是指“最大堆”。

什么是“堆”

通过上一小节的介绍，我们可以看到堆的入队和出队的时间复杂度都是 $O(\log n)$ ，因此我们可以猜测它的形状看起来像是一棵树一样。

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

堆与优先队列-1

“最大堆”的性质：

首先，“最大堆”是一棵“完全二叉树”。

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

“完全二叉树”的特点是，可以使用一个数组保存“完全二叉树”，而不必引入树形结构。这样既可以利用数组元素可以快速访问的特点，又让结点和结点之间形成了“父”与“子”的结构关系。

其次，任意一个结点，如果有孩子结点的话，孩子结点的值一定不会大于父亲结点的值。

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

下面我们从索引从 1 号开始，自上到下、自左到右，标记，即显示成结点的旁边黑色的数字，我们不难发现这些数字的排列形成的规律。正是因为“堆”是一棵“完全二叉树”，有如下的规律，我们才可以很方便地索引数组中的位置，这就是我们为什么使用数组而不是使用树来实现堆。

堆与优先队列-2

规律1：一个结点的左结点（如果有的话）的索引是这个结点的编号的 $2$ 倍；

规律2：一个结点的右结点（如果有的话）的索引是这个结点的编号的 $2$ 倍 $+ 1$ 。

从子结点索引找到父结点索引： ${\rm parent(i)}=\cfrac{i}{2}$ ，注意这里不能整除的时候需要向下取整。

从父节点索引找到两个子结点索引： ${\rm left\ child = 2 \times i}$ ， ${\rm right\ child} = 2 \times i+1$ 。

这个两条性质不用记，我们只要拿一张纸，画一个像上面一样图，就非常清楚了。到这里为止，我们可以先写出“最大堆”的框架。

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

Java 代码：

public class MaxHeap {

    private int[] data;
    private int count; // 堆中真实元素的个数

    public MaxHeap(int capacity) {
        // 开辟数组空间（整个数组存储从索引 1 开始）
        data = new int[capacity + 1];
        count = 0;
    }

    public int size() {
        return count;
    }
    // 当前堆中的元素个数是否为 0
    public boolean isEmpty() {
        return count == 0;
    }
}

下面我们介绍如何保持“最大堆”数组的堆有序的性质。

“最大堆”的第 1 个重要操作：向一个“最大堆”中添加元素

向“最大堆”中添加一个元素，对应优先队列中“入队”这个操作，同时还要保持“最大堆”的性质，即根元素是“最大堆”中最大的元素，并且除了根结点以外任意一个结点不大于它的父亲结点。这个操作叫做 shift up 。

向“最大堆”中的添加元素的时候，首先添加在数组的末尾，这是因为移动次数最少，然后进行调整，使得调整后的数组仍然满足最大堆的性质。

具体步骤如下：

1、新加的元素放在数组的末尾；

2、新加入的元素调整元素的位置：只与父结点比较（不必与兄弟孩子比较），如果比父结点大，就交换位置，否则，可以停止了，这个元素就放在当前位置。

为什么我们要在数组的末尾添加一个元素呢？可不可以在开头、中间？既然我们使用数组来实现堆，对数组添加一个元素来说，实现复杂度最低的操作就是在数组的末尾添加元素，如若不然，要让数组中一部分的元素逐个后移，因此在数组的末尾加入元素是最自然的想法。但是在数组的末尾添加了一个元素，此时的数组就不满足堆的定义（性质），我们需要进行一系列的操作，去维护堆的定义（性质）。

如何维护堆的定义和性质：通过 `shift up` 把新添加的元素放置到合适的位置

在数组的最后位置添加一个元素，新加入的元素只和父结点比较大小（无须和它的兄弟结点比较），只要比父结点大（严格大于），就往上走，否则停止，这个新添加的元素就放置在合适的位置，同时也调整了部分元素的位置。循环这样做，这样的过程叫做 shift up，shift up 也叫 swim，是“上浮”的意思。

Python 代码：

def __shift_up(self, k):
    # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
    while k > 1 and self.data[k // 2] < self.data[k]:
        self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
        k //= 2

有索引就必须要考虑索引的边界问题，就是这里说的 h > 1，因为当 h = 1 的时候，元素已经在堆顶， Shift Up 操作没有意义。

另外和“插入排序”的优化一样，先存一下这个可能会上移的元素，通过逐层赋值，实现与逐层交换上移等价的操作。

Python 代码：shift up 的过程可以转化为多次赋值

def __swim(self, k):
    # 上浮，与父结点进行比较
    temp = self.data[k]
    # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
    while k > 1 and self.data[k // 2] < temp:
        self.data[k] = self.data[k // 2]
        k //= 2
    self.data[k] = temp

shift up 是 insert 的一个子过程，有了 shift up ，insert 函数就可以很快写出来：

Python 代码：

def insert(self, item):
    if self.count + 1 > self.capacity:
        raise Exception('堆的容量不够了')
    self.count += 1
    self.data[self.count] = item
    # 考虑将它上移
    self.__swim(self.count)

最大堆的第 2 个重要操作：向一个最大堆中取出元素

根据堆有序的性质，根结点是堆（数组）中最大的元素，即索引为 $1$ 的元素。从最大堆中取出一个元素，即是取出根结点元素，同时还要保持最大堆的性质。

根结点取出以后， $1$ 号索引位置为空，于是我们将当前数组的最后一个元素放到 $1$ 号索引的位置，这样做是因为交换和移动的次数最少，这种想法也应该是十分自然的，并且保持了完全二叉树的性质，但是此时数组并不满足最大堆的性质，我们就要进行 shift down 的操作使这个数组保持最大堆的性质。

shift down 的具体操作步骤：从 $1$ 号索引开始，如果存在右孩子，就把右孩子和左孩子比较，比出最大的那个，再和自己比较，如果比自己大，就交换位置，这样的过程直到“不小于两个孩子结点中的最大者”。

同理，我们可以写出 shift down 的两个版本：

Python 代码：

def __shift_down(self, k):
    # 只要有左右孩子，左右孩子只要比自己大，就交换
    while 2 * k <= self.count:
        # 如果这个元素有左边的孩子
        j = 2 * k
        # 如果有右边的孩子，大于左边的孩子，就好像左边的孩子不存在一样
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            j = j + 1
        if self.data[k] >= self.data[j]:
            break
        self.data[k], self.data[j] = self.data[j], self.data[k]
        k = j

说明：当我们从 1 开始存放最大堆的元素的时候，最大堆的最后一个元素是 data[count]。

在完全二叉树中，如何表示有孩子？其实有左孩子就够了。这里的循环条件是 2 * k <= count ，等于号不能漏掉，自己手画一个完全二叉树就清楚了。

在结点存在子结点的情况下，先判断是否存在右孩子，如果存在右孩子，就一定有左孩子，然后把右孩子和左孩子比较，比出最大的那个，再和自己比较，如果比自己大，就交换位置，这样的过程直到“自己比左右两个孩子都大”为止。

和上一节 shift up 的优化的思路一样：逐渐下移的过程可以不用逐层交换，借用插入排序优化的思路，多次赋值，一次交换。于是，我们有了版本 2 。

Python 代码：

def __sink(self, k):
    # 下沉
    temp = self.data[k]
    # 只要它有孩子，注意，这里的等于号是十分关键的
    while 2 * k <= self.count:
        j = 2 * k
        # 如果它有右边的孩子，并且右边的孩子大于左边的孩子
        if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
            # 右边的孩子胜出，此时可以认为没有左孩子
            j += 1
        # 如果当前的元素的值，比右边的孩子节点要大，则逐渐下落的过程到此结束
        if temp >= self.data[j]:
            break
        # 否则，交换位置，继续循环
        self.data[k] = self.data[j]
        k = j
    self.data[k] = temp

shift down 是 extract_max 的一个子过程，有了 shift down，extract_max 函数就可以很快写出来。

Python 代码：

def extract_max(self):
    if self.count == 0:
        raise Exception('堆里没有可以取出的元素')
    ret = self.data[1]
    self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
    self.count -= 1
    self.__sink(1)
    return ret

完整代码：

Python 代码：

# 通过 LeetCode 第 215 题、第 295 题测试
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

    def insert(self, item):
        if self.count + 1 > self.capacity:
            raise Exception('堆的容量不够了')
        self.count += 1
        self.data[self.count] = item
        # 考虑将它上移
        self.__swim(self.count)

    def __shift_up(self, k):
        # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
        while k > 1 and self.data[k // 2] < self.data[k]:
            self.data[k // 2], self.data[k] = self.data[k], self.data[k // 2]
            k //= 2

    def __swim(self, k):
        # 上浮，与父结点进行比较
        temp = self.data[k]
        # 有索引就要考虑索引越界的情况，已经在索引 1 的位置，就没有必要上移了
        while k > 1 and self.data[k // 2] < temp:
            self.data[k] = self.data[k // 2]
            k //= 2
        self.data[k] = temp

    def extract_max(self):
        if self.count == 0:
            raise Exception('堆里没有可以取出的元素')
        ret = self.data[1]
        self.data[1], self.data[self.count] = self.data[self.count], self.data[1]
        self.count -= 1
        self.__sink(1)
        return ret

    def __shift_down(self, k):
        # 只要有左右孩子，左右孩子只要比自己大，就交换
        while 2 * k <= self.count:
            # 如果这个元素有左边的孩子
            j = 2 * k
            # 如果有右边的孩子，大于左边的孩子，就好像左边的孩子不存在一样
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                j = j + 1
            if self.data[k] >= self.data[j]:
                break
            self.data[k], self.data[j] = self.data[j], self.data[k]
            k = j

    def __sink(self, k):
        # 下沉
        temp = self.data[k]
        # 只要它有孩子，注意，这里的等于号是十分关键的
        while 2 * k <= self.count:
            j = 2 * k
            # 如果它有右边的孩子，并且右边的孩子大于左边的孩子
            if j + 1 <= self.count and self.data[j + 1] > self.data[j]:
                # 右边的孩子胜出，此时可以认为没有左孩子
                j += 1
            # 如果当前的元素的值，比右边的孩子节点要大，则逐渐下落的过程到此结束
            if temp >= self.data[j]:
                break
            # 否则，交换位置，继续循环
            self.data[k] = self.data[j]
            k = j
        self.data[k] = temp


if __name__ == '__main__':
    max_heap = MaxHeap(6)
    max_heap.insert(3)
    print(max_heap.data[1])
    max_heap.insert(5)
    print(max_heap.data[1])
    max_heap.insert(1)
    print(max_heap.data[1])
    max_heap.insert(8)
    print(max_heap.data[1])
    max_heap.insert(7)
    print(max_heap.data[1])
    max_heap.insert(12)

    while not max_heap.is_empty():
        print('取出', max_heap.extract_max())

到这里，我们就可以通过“最大堆”实现排序功能了。“最小堆”可以如法炮制。

我们已经实现了最大堆的入队和出队两个基本操作，我们完全通过直接输出元素来检验一下，自己写出的最大堆是否符合最大堆的性质。因为每一次从最大堆取出的总是数组中最大的元素，所以可以将最大堆用于排序。

优先队列的应用

1、多路归并排序

LeetCode 第 23 题：23. Merge k Sorted Lists；

传送门：23. 合并K个排序链表；

题解：https://liweiwei1419.github.io/leetcode-solution/leetcode-0023-merge-k-sorted-lists/。

2、图论中的最小生成树算法；

3、图论中的最短路径算法；

4、哈夫曼树与哈夫曼编码；

另外，在 LeetCode 上使用堆解决的问题有：

LeetCode 第 451 题：根据字符出现频率排序

LeetCode 第 703 题：数据流中的第K大元素

LeetCode 第 295 题：数据流的中位数

本文源代码

Python：代码文件夹，Java：代码文件夹。

（本节完）

最后编辑于：2019.05.24 16:35:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,332评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,508评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,812评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,607评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,728评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,919评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,071评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,802评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,256评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,576评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,712评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,389评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,032评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,798评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,026评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,473评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,606评论 2赞 350

【算法日积月累】9-堆与优先队列

【算法日积月累】9-堆与优先队列

优先队列（priority queue）

更多优先队列在生活中的例子

优先队列的主要操作

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

什么是“堆”

“最大堆”的性质：

“最大堆”的第 1 个重要操作：向一个“最大堆”中添加元素

如何维护堆的定义和性质：通过 `shift up` 把新添加的元素放置到合适的位置

最大堆的第 2 个重要操作：向一个最大堆中取出元素

优先队列的应用

本文源代码

推荐阅读更多精彩内容

【算法日积月累】9-堆与优先队列

优先队列（priority queue）

更多优先队列在生活中的例子

优先队列的主要操作

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

什么是“堆”

“最大堆”的性质：

“最大堆”的第 1 个重要操作：向一个“最大堆”中添加元素

如何维护堆的定义和性质：通过 shift up 把新添加的元素放置到合适的位置

最大堆的第 2 个重要操作：向一个最大堆中取出元素

优先队列的应用

本文源代码

推荐阅读更多精彩内容

如何维护堆的定义和性质：通过 `shift up` 把新添加的元素放置到合适的位置