algorithm - heapify 在左派堆队列上的复杂性

Question

Tarjan 的“数据结构和网络算法”在最左边的堆中声明 heapify 函数如下：

heap function heapify (list q);
  do |q| ≥ 2 → := q[3..] & meld (q(1), q(2)) od;
  return if q = [ ] → null | q != [ ] → q(1) fi
end heapify;

q是我们想一起堆的堆队列。meld(h1, h2)是一个合并两个堆并恢复堆属性的函数。meld(h1, h2)具有复杂性O(logn)，其中n是两个堆中的节点总数。这使得一次通过队列的复杂性如下：

（等式 1）

这是合理的。我没有得到的是整个 heapify 的时间：

（等式 2）

k这是原始堆n的数量和它们包含的项目总数。前面还提到了两个约束：

（等式 3）

有人可以帮我理解 Eq. 2是派生的？（如何解释等式 2 中等式的左表达式）

Answer 1

我想出了解决方案，结果很明显：

在每次迭代中，队列元素的数量减半。这使得它每次迭代 k/2。查看所有迭代，该数字以指数方式缩小到 2 的底数，即对于 i=0，我们有 k；i=1k/2；i=2k/4；i=3 k/8 所以这就是为什么总和会上升到 lg k 并且堆的数量会减少 k/(2^i)。方程式中的总和。3 告诉我们，所有元素都分布在当前运行的堆之间。正如我们刚刚发现的，每次迭代的堆数为 k/(2^i)。这就是为什么每次队列运行的最大融合为 n_i = n/(k/(2_i)) = n*(2_i)/k。所有这些共同解释了方程式。2 去掉常数后，我们得到右边的方程。