美文网首页
一分钟了解堆的基本操作

一分钟了解堆的基本操作

作者: 码农田小齐 | 来源:发表于2020-10-07 09:40 被阅读0次

基本操作

任何一个数据结构,无非就是增删改查四大类:

功能 方法 时间复杂度
offer(E e) O(logn)
poll() O(logn)
无直接的 API 删 + 增
peek() O(1)

这里 peek() 的时间复杂度很好理解,因为堆的用途就是能够快速的拿到一组数据里的最大/最小值,所以这一步的时间复杂度一定是 O(1) 的,这就是堆的意义所在。

那么我们具体来看 offer(E e)poll() 的过程。

offer(E e)

比如我们新加一个 0 到刚才这个最小堆里面:

那很明显,0 是要放在最上面的,可是,直接放上去就不是一棵完全二叉树了啊。。

所以说,

  • 我们先保证加了元素之后这棵树还是一棵完全二叉树,
  • 然后再通过 swap 的方式进行微调,来满足堆序性。

这样就保证满足了堆的两个特点,也就是保证了加入新元素之后它还是个堆

那具体怎么做呢:

Step 1.

先把 0 放在最后接上,别一上来就想着上位;

OK!总算先上岸了,然后我们再一步步往上走。

这里「能否往上走」的标准在于:
是否满足堆序性

也就是说,现在 5 和 0 之间不满足堆序性,那么交换位置,换到直到满足堆序性为止

这里对于最小堆来说的堆序性,就是小的数要在上面

Step 2. 与 5 交换

此时 0 和 3 不满足堆序性了,那么再交换。

Step 3. 与 3 交换

还不行,0 还比 1 小,所以继续换。

Step 4. 与 1 交换

OK!这样就换好了,一个新的堆诞生了~

总结一下这个方法:

先把新元素加入数组的末尾,再通过不断比较与 parent 的值的大小,决定是否交换,直到满足堆序性为止。

这个过程就是 siftUp(),源码如下:

时间复杂度

这里不难发现,其实我们只交换了一条支路上的元素,

也就是最多交换 O(height) 次。

那么对于完全二叉树来说,除了最后一层都是满的,O(height) = O(logn)

所以 offer(E e) 的时间复杂度就是 O(logn) 啦。

poll()

poll() 就是把最顶端的元素拿走。

对了,没有办法拿走中间的元素,毕竟要 VIP 先出去,小弟才能出去。

那么最顶端元素拿走后,这个位置就空了:

我们还是先来满足堆序性,因为比较容易满足嘛,直接从最后面拿一个来补上就好了,先放个傀儡上来。

Step1. 末尾元素上位

这样一来,堆序性又不满足了,开始交换元素。

那 8 比 7 和 3 都大,应该和谁交换呢?

假设与 7 交换,那么 7 还是比 3 大,还得 7 和 3 换,麻烦。

所以是与左右孩子中较小的那个交换。

Step 2. 与 3 交换

下去之后,还比 5 和 4 大,那再和 4 换一下。

Step 3. 与 4 交换

OK!这样这棵树总算是稳定了。

总结一下这个方法:

先把数组的末位元素加到顶端,再通过不断比较与左右孩子的值的大小,决定是否交换,直到满足堆序性为止。

这个过程就是 siftDown(),源码如下:

时间复杂度

同样道理,也只交换了一条支路上的元素,也就是最多交换 O(height) 次。

所以 offer(E e) 的时间复杂度就是 O(logn) 啦。

那以上就是有关堆的基本操作啦!对于堆,还有一个比较特别的操作,就是 heapify(),这是一个很神奇的操作,至于神奇在何处、为什么它能做到、它是怎么做到的,我们下一篇文章再说~

如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE

相关文章

  • 一分钟了解堆的基本操作

    基本操作 任何一个数据结构,无非就是增删改查四大类: 功能方法时间复杂度增offer(E e)O(logn)删po...

  • 堆的基本操作

    堆的基本概念: 严格来讲,堆有不同的种类,但是我们在算法学习中,主要用的还是二叉堆,而二叉堆有最大堆和最小堆之分。...

  • 堆的基本操作与堆排序(C/C++实现)

    原理参考:堆和堆排序原理介绍 堆的基本操作(以最小堆为例) 基本数组的定义 向下调整操作 向下调整操作一般是针对一...

  • 2018-09-21

    作业说明 了解并学会git的基本操作以及学习git的意义 学会使用Markdown,了解各项基本操作,并用Mark...

  • 京东工作总结

    20160613 工作内容:熟悉系统熟悉公司基本操作 收获A:基本操作,与同事初步认识,公司文化基本了解 2016...

  • 为什么堆化 heapify() 只用 O(n) 就做到了?

    heapify() 前面两篇文章介绍了什么是堆以及堆的两个基本操作,但其实呢,堆还有一个大名鼎鼎的非常重要的操作,...

  • 堆操作

    测试1: 测试2:

  • 实验三

    实验三 Linux基本操作实例再现 实验目的 1.进一步了解Linux操作系统,掌握基本的Linux操作。 2...

  • Python文件处理 - 专题笔记

    任何语言都离不开对文件的操作,Python语言是如何来操作和管理文件的。掌握文件的基本概念、基本操作,了解文件属性...

  • Linux系统介绍和RHEL7.2操作系统的安装

    内容介绍 • VMware workstation的基本使用 • RHEL7 基本了解 • RHEL7.1操作系统...

网友评论

      本文标题:一分钟了解堆的基本操作

      本文链接:https://www.haomeiwen.com/subject/pgffpktx.html