8元素二進制堆需要多少次比較？

Question

這是一個家庭作業問題，我要求顯示8元素二進制堆需要8個比較。

但是當我使用這樣一個例子：1 2 3 4 5 6 7 8 我不知道我是否應該自下而上或自上而下。 但無論如何，我已經嘗試過他們兩個。

在自上而下： 我已經做了8級，但是當我算比較的次數，我得到13：S

在bottum起來： 我已經在7個步驟完成，但是當我算餘得到10比較的次數：S

這裏試圖算法之後是我得到了比較：

1. H [L] = 8> H [I] = 4
2. ħ[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. ħ [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 log n)。

試着按照實際的算法，不要畫樹。我已經看到，在太多的考試中，人們畫美麗的樹木，但沒有遵循alogrithm，這往往導致不正確的結果，效率低下等。樹只是'想法'，而不是'方法'。這裏的方法實際上使用了一個數組。

編輯：自底向上從堆大小的一半開始。因此，在元件1,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比較。確切的範圍，檢查一本教科書。

Answer 2

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

建立一個自下而上的堆實際上是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 
    E   B 
    G F  D C 
H 

而且我們完成了，我們有8個元素構建的8堆比較堆。希望一切都可以理解hahaha