如何證明子節點的heap堆：第i個節點有2個孩子是2i和2i + 1？

Question

很容易看出公式是正確的，但我不知道如何證明這一點。那麼其他一些樹如：每個節點有3個孩子，4個孩子的樹......？ 謝謝！

Answer 1

您必須證明，如果在一級序遍歷滿二叉樹，你會經常訪問你的n第一次在2n次和第2n+1次訪問節點的孩子。

我們可以通過歸納來做到這一點。證明的基本情況很簡單：

1 
/ \ 
2  3 

現在，我們必須證明，如果它是一些n真實的，它也是n+1真：

如果我們訪問的n孩子們在2n和2n+1時間，n+1的孩子將在他們旁邊，被訪問時間2n+2 = 2(n+1)和2n+3 = 2(n+1)+1。

Q.E.D.

  . 
      . 
      . 

    n   n+1 
/ \  / \ 
2n 2n+1 2n+2 2n+3 

的圖像僅僅是一個例子，n和n+1可以位於不同的高度。這沒有問題。 n和n+1的孩子將始終是鄰居，因爲執行級別順序的方式（訪問節點並將孩子添加到隊列中）。

Answer 2

它更像是一個定義而不是一個證明：你定義它就是這樣，然後你在確保你保持在你定義的不變範圍內的同時使用它。你可能想要證明沒有重疊，但這很容易看到。

對於3個孩子，我們可以使用3i, 3i+1, 3i+2：

  1 
     /| \ 
     2 3 4 -- 
      | \ \ 
      5 6 7 

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 
label: - - 2 3 4 - - - - - - 5 6 7 

然而，正如你所看到的，這得到相當低效。如果你能負擔得起內存，它可能會比使用指針更快，但否則它將不會很有用。