algorithm - 插入二进制堆 : Number of exchanges in worst case

Question

我正在阅读 Cormen 的“算法解锁”。在关于最短路径算法的第 6 章中，关于将数据插入二进制堆，我发现:“由于到根的路径最多有 floor(lg(n)) 条边，因此最多有 floor(lg(n))-1发生交换，因此 INSERT 需要 O(lg(n)) 时间。”现在，我知道在二叉堆中插入的结果复杂度如前所述，但关于最坏情况下的交换次数，应该不是 floor(lg(n)) 而不是 floor(lg(n))-1 .这本书的勘误表对此只字不提。所以我想知道我是否遗漏了什么。

感谢和问候，阿迪亚

Answer 1

您可以很容易地证明它是floor(lg(n))。考虑这个二进制堆:

    3
  5  7

要插入值 1，首先要将它添加到堆的末尾:

    3
  5  7
1

所以堆中有 4 个项目。需要两次交换才能将项目 1 移动到根目录。 floor(lg(4)) 等于 2。