「优先队列」专题 1:优先队列与堆


「队列」专题 1:优先队列与堆

这部分我们介绍一种新的数据结构堆(Heap),「堆」是实现「优先队列」的一个高效的数据结构。首先,我们来认识「优先队列」。

优先队列

  • 优先队列(Priority Queue)是一种数据结构;
  • 堆(Heap)是具体的实现。

知识结构:

优先队列(priority queue)

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

例:班级里要选一名同学代表全班参加程序编程竞赛,此时我们只会关心第 1 名是谁,第 1 名本人不想参赛了,或者说第 1 名因为其它因素不符合参考资格,我们才考虑第 2 名,但也是从剩下的那些同学中挑出第 1 名。

即当前我们只关心当前「最优」的那个元素,第 2 名及其以后的同学都不考虑了。

「优先队列」相对于「普通队列」而言。「普通队列」的性质是「先进先出,后进后出』。「优先队列」由元素的优先级决定出队的顺序。

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

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

「优先队列」更多地应用于动态的情况,即数据不是一开始就定好的,而是随时都有可能来新的数据,此时新数据与旧数据在一起选出「优先级」最高的那个元素。比如以下场景,重点理解「动态执行」这个概念:

1、医院看病:重症患者往往优先治疗,即使他是后来者;

2、操作系统:选择优先级最高的任务执行;

3、上网:服务端依次回应客户端的请求:通常也是使用优先队列,优先级高的客户端优先响应;

下面是一个静态的例子。

例:从 $1000000$ 个数中选出最大的 $100$ 个数。

这个问题我们抽象成数学表达就是:在 $N$ 个元素中选出前 $M$ 个元素。

1、如果我们使用之前学习的排序算法,时间复杂度为:$O(N \log N)$,即先排序,再取出前 $M$ 个元素。此时,这个问题的时间复杂度完全由使用的排序算法决定。

2、如果我们使用优先队列,那么解决该问题的时间复杂度为:$O(N \log M)$。与使用排序算法不同之处在于,我们只要维护有 $M$ 个元素的数据结构就可以了。在这一章的末尾我们将要解决这样的问题。

优先队列的主要操作

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

  • 一种「优先队列」每次可以从中拿到我们定义下优先级「最高」的元素,即「最大堆」、「大顶堆」、「大根堆」;
  • 另一种「优先队列」每次可以从中拿到我们定义下优先级「最低」的元素,即「最小堆」、「小顶堆」、「小根堆」。如果没有特别说明,我们下文所指的「优先队列」都是指每次可以拿到优先级「最高」元素的优先队列。

「优先队列」的主要操作有:

  • 入队;
  • 出队:优先队列的一个重要特点是:出队的时候总是取出优先级最高的那个元素

优先队列的几种实现方式

如果不考虑时间复杂度,「优先队列」可以有以下两种实现方式:「无序数组」和「有序数组」。

实现 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)$。

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

优先队列的应用

1、多路归并排序

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

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

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

另外,在「力扣」上使用堆解决的问题有:

本文源代码

(本节完)

堆是一种定义在数组上的「树」结构,设计很巧妙。是我刚开始喜欢上的「数据结构」。

认识优先队列(Priority Queue)与堆(Heap)

通过上一小节的介绍,我们可以看到堆的入队和出队的时间复杂度都是 $O(\log n)$ ,因此我们可以猜测它的形状一定看起来像是一棵树一样。根据我们希望出队的元素是整个队中最大的那个元素或者是最小的那个元素来划分堆,我们可以将堆分为最大堆和最小堆。

在这里说一个说明,对于一般教科书上已经有的,或者给出名词就很好理解的概念,我们在这里就不重复描述了,因为那样做就只是在抄书而已,虽然那样做会让我的描述变得很严谨,但会显得这篇文章很长,不方便阅读和复习,我们写出来的,都只是一些必要的,关键的,在我的学习中觉得难以理解的地方。

我们完全可以通过对一个例子的描述,来认识堆。以下就是一个最大堆的例子。

二叉堆 Binary Heap 的特点

1、这是一棵树;

2、最大的元素在树根,这个元素就是我们上面所说的优先级最高,最重要的那个元素,我们出队就应该把它出队列出拿出来(这种操作有的时候又叫做“删除”,这并不难理解,我们处理完一个任务,就应该把它从我们的任务清单中划去);

3、把每一棵子树单独拿出来看,孩子结点小于父结点,换句话说,父亲结点一定比孩子结点大(为了避免问题复杂化,我们假设进入堆中的元素互不相同);

4、堆是一棵完全二叉树

完全二叉树的性质:从形状上看,除了最后一层之外,其它层结点的数量应该是最大值,并且最后一层的结点应该集中在左侧。

马上我们就可以看到,完全二叉树这个性质为我们定位这棵树上的结点位置提供了方便

看到这里,或许我们在脑子里有个疑问,那么既然堆是一棵树,我们是不是要把堆实现成一个一个结点和指针组成的树呢?其实是可以的,但是我们还注意到堆是一棵完全二叉树,因此把堆用数组存起来会更加方便,因为在一般意义上,操作数组的下标,比操作结点和指针要方便一些,这一点我们马上就会看到。

使用数组实现二叉堆

由于最大堆是一颗完全二叉树,我们可以使用「树」这个数据结构来实现。但是,最大堆的一个经典的实现是:使用数组存储二叉堆。使用数组实现二叉堆的方式是:自上到下、自左到右对下标进行标记,0 号下标不使用,从 1 号下标开始使用(这是一种经典的做法)。

之所以,0 号下标不使用,是因为从 1 开始下标,对于二叉堆来说,有比较简单的性质。不过根据我们应用的场景,我们也会使用从 0 号下标 开始的最大堆。

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

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

  • 重要性质1:一个结点的左结点的下标是这个结点的编号的 2 倍;
  • 重要性质2:一个结点的右结点的下标是这个结点的编号的 2 倍 + 1。

因此,要想找到父结点:${\rm parent(i)}=\cfrac{i}{2}$,注意这里不能整除的时候需要向下取整。

要想找到两个子结点:${\rm left\ child = 2 \times i}$,${\rm right\ child} = 2 \times i+1$。

这个两条性质不用记,我们只要拿一张纸,画一个草图,这个性质就一目了然了。

体会使用数组来表示一个完全二叉树的好处

在这里啰嗦一句,如果我们使用树结构来保存上面那张图的数据,我们要创建 10 个结点,并且还要指明它们之间的引用关系,那样做显然就太复杂了。下面给出了使用数组实现最大堆的一个基本实现框架。


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「队列」专题:队列与广度优先遍历 「队列」专题:队列与广度优先遍历
「队列」专题:队列与广度优先遍历队列 Queue 主要处理的问题是广度优先遍历(不论是针对树还是图,可以把树理解为图的特殊形式)。
下一篇 
「力扣」第 739 题:每日温度(单调栈)(单调栈) 「力扣」第 739 题:每日温度(单调栈)(单调栈)
「力扣」第 739 题:每日温度(单调栈)链接:https://leetcode-cn.com/problems/daily-temperatures 题解链接:https://leetcode-cn.com/problems/daily-
  目录