优先队列的核心,面试的常客,带你深入了解堆-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

优先队列的核心,面试的常客,带你深入了解堆

简介:

云栖号资讯:【点击查看更多行业资讯
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!


今天是算法和数据结构的第21篇,我们来聊一个新的数据结构——堆(heap)。

和链表、二叉树以及数组这些热门的数据结构相比,堆相对比较冷门。如果你对数据结构了解不深的话,可能很少听说。但是我们经常用到它,虽然可能你并不一定能感知到。比如说优先队列,我们就经常使用。我们需要用到这样一个数据结构,能够根据我们存入数据的优先级进行排序,将优先级高的排在前面。在和调度相关的一些系统和算法当中,优先队列是必然会用到的。但是很少有人知道,优先队列说是一个队列,但其实是通过堆实现的。

那么堆究竟是一个怎样的数据结构呢?

堆的定义

堆的实质其实是二叉树,并且还不是一般的二叉树,而是比较特别的二叉树。

特别在什么地方呢,在于这棵二叉树除了叶子之外的所有节点都是“满”的。所谓的满,也就是没有空缺的意思。

1

从上图当中我们可以看到,如果去掉最后一层,那么这棵二叉树就是全满的。最后一层叶子节点也是有要求的,要求叶子节点都靠左对齐。满足这两个条件的二叉树成为完全二叉树(complete binary tree)。这个概念如果记不住也没有关系,我好像也只在堆当中遇到。

堆是完全二叉树,但是显然不是所有的完全二叉树都是堆,堆还有一个特殊的性质,就是大小的传递性。

堆根据大小传递性的不同分为大顶堆和小顶堆,所谓的大顶堆就是堆顶的元素也就是树根的元素是最大的。如果是小顶堆则相反,堆顶元素是最小的。所以这两者基本一样,我们就以大顶堆举例。这个传递性其实很好理解,其实只有一条,就是所有节点的值大于它两个孩子的值。也就是说从树根到树叶每一条路径都是递减的。

我们可以看下这张图:

2

100有两个孩子节点,19和36,100比19和36都大。19有两个孩子17和3,19比它们都大。这应该是很好理解的,堆巧妙的点在哪里呢,巧妙的点在于我们可以用数组来存储这个结构,而不需要自己建树。用数组存储的方法也很简单,我们给图上的点标上下标,可以得到:

3

我们找下规律,可以发现对于一个树上的一个节点,假设它在数组当中的下标是i的话。那么它的左孩子的下标是i 2 + 1, 它的右孩子下标为i 2 + 2,它的父节点是(i - 1) // 2。

有了这个规律之后,我们只要知道某个点的坐标,就可以知道它的父亲和两个孩子的坐标。这也是用数组来存储堆非常巧妙和方便的点。

堆的插入

有了这个性质有什么用呢?其实很有用,我们可以利用它非常方便地完成堆的维护。

想象一下,首先,往堆的末尾插入元素并不会破坏完全二叉树这个性质。因为完全二叉树的叶子节点是往左对齐的,我们插入元素必然也是在最左边,所以不管我们插入的元素数值是多大,这都不会影响完全二叉树这个性质。但是显然,我们插入的数值大小会影响堆结构的正确性,比如如果我们插入9,插入的位置就不满足大顶堆的性质了。

4

这个时候,为了维护堆的性质我们需要调整当中的数据。所以其实堆插入元素的过程就是一个调整顺序的过程,那怎么调整呢,其实很简单,就是将我们插入的元素向上比较,如果它比它的父节点元素更大,那么就将它和父节点进行交换,一直到它小于父节点或者是它称为堆顶为止。

假如说,我们插入的元素不是9,而是105,那么最后得到的结果应该是这样的:

5

这个就是堆的插入过程,因为我们只有插入的位置可能会导致破坏堆结构,所以我们只需要从插入的位置开始往上维护即可。其余的位置并不会影响,并且对于整个这条链路上可能会被影响的节点而言,它们只可能变大,不可能减小,因此也不会出现交换了之后有新的不满足堆性质的情况产生。

由于这个插入的过程是自下而上的,因此整个过程也被称为是向上更新。

我们来看下向上维护的代码,只有几行,非常简单:

6

理解了堆的插入之后,那么堆的建立也应该很好理解了。所谓建堆的过程,其实就是将元素一个一个插入堆当中的过程。

我们利用maintain方法,很容易实现建堆的过程。

7

堆的查询与弹出

堆和其他数据结构不同,它对于数据的查询非常有限,只允许查询堆顶的元素。如果是大顶堆就是允许查询最大元素,否则则是允许查询最小元素。同样,也只允许删除堆顶的元素,由于删除堆顶的元素好像挤牙膏一样将元素挤出去一样,所以也称为“弹出”(pop)。

只是查询很好理解,我们返回数组下标为0的元素即可,但是如果是弹出该怎么办呢?弹出了之后,不是堆顶元素就空缺了吗?产生空缺了之后怎么办呢?

一种办法是从根节点的孩子当中选择一个作为替补顶上来,但是替补顶上之后又会产生新的空缺,这样一调整可能完全二叉树的性质就保不住了。所以只有一个办法,也很直观,就是将末尾的元素拿出来作为替补放到堆顶。但是显然末尾的元素不是最大的,所以这样操作之后还需要调整。

怎么调整呢?

当然是从堆顶开始将它和左右孩子进行比较,如果左右孩子当中存在比它大的,那么就交换,将这个元素往下传递。比如下图当中,我们弹出堆顶的元素100,根据算法的逻辑,我们会用末尾的7作为替补。

8

第一次我们将它和19与36进行比较,由于要满足大顶堆的性质,我们选择其中最大的36交换。于是我们将7往下传递到了原来36的位置,我们继续将它和两个孩子节点进行比较。我们发现25大于7,于是我们继续交换,这个时候到达了叶子节点,停止。

我们再反观维护之后的结果,仍然满足大顶堆的性质,并且仍然是一棵完全二叉树。和刚才插入时候的维护进行对比,我们会发现其实这整个过程是一个向下更新的过程。堆这个数据结构的核心其实就在这两个更新当中,在插入的时候向上更新,在弹出的时候向下更新。

代码也非常简单:

01

02

堆与优先队列

到这里,整个堆的主体部分就实现完了。整个过程还是比较直观的,并不复杂,只要记住了两个更新就足够了。

理解了堆之后我们再来看优先队列,我们使用优先队列的时候,希望每次取出优先级最大的数据,然后当我们填入数据的时候,队列会自动根据我们设置的优先级对数据进行排序。这不刚好就是堆的功能吗?所以通过堆,我们可以很方便地实现优先队列,当然我们没有必要这么做,因为在Python当中为我们封装了现成的堆,我们只需要调用它,就可以很轻松地自己封装一个优先队列。

9

如果你愿意,你还可以往这个类当中加入一些其他的辅助函数。当然,我还是建议大家,都能自己从头用堆实现一个属于自己的优先队列,体会一下亲手实现数据结构的成就感。

堆很实用,也不难写,希望大家都能体会到手撸数据结构的快乐。

【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live

立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK

原文发布时间:2020-05-25
本文作者:承志
本文来自:“掘金”,了解相关信息可以关注“掘金”

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章