任何一个数据结构,无非就是增删改查四大类:
功能 | 方法 | 时间复杂度 |
---|---|---|
增 | offer(E e) | O(logn) |
删 | poll() | O(logn) |
改 | 无直接的 API | 删 + 增 |
查 | peek() | O(1) |
这里 peek()
的时间复杂度很好理解,因为堆的用途就是能够快速的拿到一组数据里的最大/最小值,所以这一步的时间复杂度一定是 O(1)
的,这就是堆的意义所在。
那么我们具体来看 offer(E e)
和 poll()
的过程。
比如我们新加一个 0
到刚才这个最小堆里面:
那很明显,0 是要放在最上面的,可是,直接放上去就不是一棵完全二叉树了啊。。
所以说,
这样就保证满足了堆的两个特点,也就是保证了加入新元素之后它还是个堆。
那具体怎么做呢:
先把 0 放在最后接上,别一上来就想着上位;
OK!总算先上岸了,然后我们再一步步往上走。
这里「能否往上走」的标准在于:
是否满足堆序性。
也就是说,现在 5 和 0 之间不满足堆序性,那么交换位置,换到直到满足堆序性为止。
这里对于最小堆来说的堆序性,就是小的数要在上面。
此时 0 和 3 不满足堆序性了,那么再交换。
还不行,0 还比 1 小,所以继续换。
OK!这样就换好了,一个新的堆诞生了~
总结一下这个方法:
先把新元素加入数组的末尾,再通过不断比较与 parent 的值的大小,决定是否交换,直到满足堆序性为止。
这个过程就是 siftUp()
,源码如下:
这里不难发现,其实我们只交换了一条支路上的元素,
也就是最多交换 O(height)
次。
那么对于完全二叉树来说,除了最后一层都是满的,O(height) = O(logn)
。
所以 offer(E e)
的时间复杂度就是 O(logn)
啦。
poll()
就是把最顶端的元素拿走。
对了,没有办法拿走中间的元素,毕竟要 VIP 先出去,小弟才能出去。
那么最顶端元素拿走后,这个位置就空了:
我们还是先来满足堆序性,因为比较容易满足嘛,直接从最后面拿一个来补上就好了,先放个傀儡上来。
这样一来,堆序性又不满足了,开始交换元素。
那 8 比 7 和 3 都大,应该和谁交换呢?
假设与 7 交换,那么 7 还是比 3 大,还得 7 和 3 换,麻烦。
所以是与左右孩子中较小的那个交换。
下去之后,还比 5 和 4 大,那再和 4 换一下。
OK!这样这棵树总算是稳定了。
总结一下这个方法:
先把数组的末位元素加到顶端,再通过不断比较与左右孩子的值的大小,决定是否交换,直到满足堆序性为止。
这个过程就是 siftDown()
,源码如下:
同样道理,也只交换了一条支路上的元素,也就是最多交换 O(height)
次。
所以 offer(E e)
的时间复杂度就是 O(logn)
啦。
那以上就是有关堆的基本操作啦!对于堆,还有一个比较特别的操作,就是 heapify()
,这是一个很神奇的操作,至于神奇在何处、为什么它能做到、它是怎么做到的,我们下一篇文章再说~
如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!
我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!
更多干货文章见我的 Github: https://github.com/xiaoqi6666/NYCSDE