在做微服务设计的时候需要DDD？

样整个 heapify() 的过程就完成了。

好了难点来了，为什么时间复杂度是 O(n) 的呢?

怎么计算这个时间复杂度呢?

其实我们在这个过程里做的操作无非就是交换交换。

那到底交换了多少次呢?

没错，交换了多少次，时间复杂度就是多少。

那我们可以看出来，其实同一层的节点最多交换的次数都是相同的。

那么这个总的交换次数 = 每层的节点数 * 每个节点最多交换的次数

 

所以我们没有办法直接使用。

唯一使用 heapify() 的方式呢，就是使用PriorityQueue(Collection c)

这个 constructor 的时候，人家会自动调用 heapify() 这个操作。

那具体是怎么做的呢?

哈哈源码已经暴露了：

从最后一个非叶子节点开始，从后往前做 siftDown().

因为叶子节点没必要操作嘛，已经到了最下面了，还能和谁 swap?

举个例子：

 

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

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

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

poll()

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

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

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

 

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

所以说，

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

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

那具体怎么做呢：

Step 1.

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

（编辑：保山站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!