algorithm - 8 元素二叉堆需要多少次比较？

Question

这是一道作业题，要求我证明 8 元素二叉堆需要 8 次比较。

但是当我使用这样的例子时:1 2 3 4 5 6 7 8 我不确定我应该自下而上还是自上而下。 但无论如何，我都试过了。

自上而下: 我分 8 个步骤完成了，但是当我计算比较次数时，我得到 13 :S

自下而上: 我已经分 7 个步骤完成了，但是当我计算比较次数时，我得到 10 :S

在这里尝试算法后是我得到的比较:

1. H[L]=8 > H[i]=4
2. H[L]=8 > H[i]=2, H[r]=5 > H[最大]=8
3. H[L]=4 > H[i]=2
4. H[L]=6 > H[i]=3, H[r]=7 > H[最大]=6
5. H[L]=8 > H[i]=1, H[r]=7 < H[最大]=8
6. H[L]=4 > H[i]=1, H[r]=5 > H[最大]=4

嗯，关于我应该如何计算比较次数以便显示 8 有什么帮助吗？ 我应该使用什么方法(自下而上或自上而下)？

Answer 1

我认为接受的答案不正确。

自下而上构建堆实际上是 O(n)，但这只是适用于一般情况的上限。有可能在特定情况下表现得更好，例如当我们有 8 个元素时。我将在下面展示至少一种可以在 8 次比较中构建 8 个元素的堆的方法。

假设我们有 8 个元素 {A、B、C、D、E、F、G、H}，我们对它们的相对顺序一无所知。我们首先比较八个元素中的任意四对。在这一步之后，我们进行了 4 次比较，现在有 4 个“有序”对，如下所示:

A > B, C > D, E > F, G > H

现在，请注意，通过 1 次比较，我们可以将两对放在 N = 4 的树中。例如，如果我们取前两对并比较 A 和 C，我们最终会得到左边的树下方(如果 A > C)或右侧(如果 C > A):

    A     |       C 
  C   B   |     A   D
D         |   B

我们对其他两对应用相同的过程，到目前为止使用 6 次比较得到两棵 N = 4 的树。我们有这样的东西:

    A              E 
  C   B   and    G   F
D              H

通过一次额外的比较，我们可以决定 A 或 E 之间哪个具有更高的顺序。假设 A > E 不失一般性。到目前为止，我们已经使用了 7 次比较。最后，我们使用最后一次比较左边来决定 A 下面的元素(B 和 C)之间的顺序，并使用该信息将上面左边的树重新排列为下面的两个之一(左边的 B > C，C > B在右边):

 A        |   A     
   B      |     C   
 C   D    |   B   D

最后，由于我们已经知道 A > E，现在很容易加入我们拥有的两棵树(一棵以 E 为根，一棵以 A 为根)，如下所示:

         A
    E         B
  G   F     D   C
H

我们完成了，我们有一个由 8 个元素组成的堆，经过 8 次比较。希望一切都可以理解哈哈哈