2

这是一个家庭作业问题，我被要求展示 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 的任何帮助？我应该使用什么方法（自下而上或自上而下）？

4

2 回答 2

9

我相信接受的答案是不正确的。

自下而上构建堆实际上是 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 次比较。最后，我们使用最后的比较 left 来确定 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 个比较。希望一切都可以理解哈哈哈

于 2015-08-15T23:37:59.157 回答
1

自下而上构建堆是线性的，自上而下（或增量）是O(n log n).

尝试遵循实际的算法，不要只画树。我已经看到在太多的考试中，人们画了漂亮的树但没有遵循算法，这通常会导致错误的结果、低效率等。树只是“想法”，而不是“方法”。这里的方法实际上使用了一个数组。

编辑：自下而上从堆大小的一半开始。所以在元素 4 和 7 比较：

Level 3: 4 < 8
Level 2: 3 < 7, 3 < 6
         2 < 5, 2 < 4
Level 1: 1 < 3, 1 < 2

Edit2：最大堆：

Level 3: 4 < 8 -> Swap 4-8.
Level 2: 3 < 7, 3 < 6 -> Swap 3-7, fix heap down (no-op)
         2 < 5, 2 < 8 -> Swap 2-8, fix heap down:
           2 < 4 -> Swap 2-4, fix heap down (no-op)
Level 1: 1 < 7, 1 < 8 -> Swap 1-8, fix heap down
           1 < 4, 1 < 5 -> Swap 1-5, fix heap down (no-op)
Resulting heap:
          8
      5       7
    4   1   6   3
   2

进行 10 次比较。所以我相信要么你的作业问题有错误，要么你错误地报告了这个问题。自下而上构建堆O(n)并不意味着它需要完全n比较。有关确切的界限，请查看教科书。

于 2011-12-24T21:51:43.913 回答