前言

今天要進入的章節是 Binomial Heap，本章節會從 Binomial Tree 談起，再談相關的數學公式、證明，才會進入介紹我們真正今天要講的主題 Binomial Heap

Binomial Tree 定義

先假設 root 之 level 由 0 開始

1. 高度為 0，由單顆 node 組成的 Binomial Tree
2. 高度為 k，由兩顆 所組成的 Binomial Tree

相關數學公式

1. 第 i 層的 node 個數 :

利用數學歸納法證明：

• 令 i=0，高度為 0 之 Binamial tree，共 =1 個 Node
• 推到 i = i-1 皆成立
• 當 i=k， 高度為 k，由兩顆 ，第 i level 的 Node 數可以推成 +

2. 總 Node 數 :

利用數學歸納法證明：

• 令 k=0 為 1 顆 Node
• 推到 k-1 皆成立
• 

定義 Binomial Heap

即為多個 Binomial Tree 所組成的 Forest，每棵 Tree 都是 Min Tree
若我們限定此 Heap 中每顆樹高度不一，就有從節點個數，便可以知道組成的 Binomial Tree 有哪些的特性
剛剛提過 總 Node 數就是2的次方，因此我們把 n 換成 2進制，就可以知道有哪些 Binomial Tree 了

以上圖為例，這四個 Binomial Tree 組成 Binomial Heap，個數為 2^0 + 2^1 + 2^2 + 2^3，看成 2 進制即為 (2222)，因此我們可以知道 Forest 裡面有哪些 Binomial Tree