关于java:一分钟了解堆的基本操作

基本操作

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

这里 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...