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

Question

Tarjan 的“数据结构和网络算法”在 leftiest heaps 中陈述了 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)

这是合理的。我没有得到的是整个堆化的时间:

(等式 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 和 s.o.这就是总和上升到 lg k 而堆的数量减少 k/(2^i) 的原因。方程式中的总和。 3 告诉我们，所有元素都分布在当前运行的堆之间。正如我们刚刚发现的那样，每次迭代的堆数为 k/(2^i)。这就是为什么每次队列运行的 meld 最大值为 n_i = n/(k/(2_i)) = n*(2_i)/k。所有这些共同解释了方程式。 2 去掉常数后，我们得到右边的方程。