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个比较构建.希望一切都是可以理解的哈哈哈