一分钟了解堆的基本操作

1,276 阅读4分钟

基本操作

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

功能 方法 时间复杂度
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