algorithm - SiftDown 算法比较次数

Question

我最近正在研究siftDown用于构建二进制堆的算法。在“算法和数据结构：基本工具箱”一书中练习 6.5 中指出，该算法的给定实现需要2*log(n)元素比较。现在，我试图弄清楚为什么会这样，但我做不到。为什么这是正确的？

Answer 1

调用时siftDown(i)，您首先执行两个元素比较：

• 第一个是h[2i]和之间h[2i+1]。
• 第二个是h[i]和之间h[m]。

进行两次比较后，您递归调用siftDown(m)wherem=2i或m=2i+1。也就是说，每次siftDown()使用n-element 堆调用都会导致进行两次元素比较和对siftDown()-elementn/2堆的调用。

因此，使用-element 堆T(n)调用时进行的比较次数满足：siftDown()n

T(n) = 2 + T(n/2)

这种递推关系的解是

T(n) = 2logn

您可以2logn通过观察每次都恰好进行 2 个元素比较，并且次数为logn（因为如果您开始n并不断除以 2，那么您就完成了）logn部门）。

因此，由 进行的元素比较总数siftDown()约为2logn.