定義:由一些Binomial tree組成，滿足heap性質，具以下特徵: 1、B 的Binomial tree具有B 個Bnomial tree K K-1 (就是B1由B0組成，B2由B1、B0組成，B3由B2 B1 B0見下圖 ) k 2、B的Binomial tree具有2 個節點 高度 ○ ∥ ○ ∥ ○ ∥ ○ -----------0 ∥ │ ∥ ╱ ╲ ∥ ╱︱╲ ∥ ○ ∥ ○ ○ ∥ ╱ ︱ ╲ ∥ ∥ │ B0 ∥ ○ ○ ○------1 ∥ ∥ ○ ∥ ╱︱ │ B0 ∥ ∥ B1 ∥ ○ ○ ○------------2 ∥ ∥ ∥ │ B1 ∥ ∥ ∥ ○--------------------3 ∥ ∥ ∥ B2 ∥ ∥ ∥ B0 ∥ B1 ∥ B2 ∥ B3 3.Bk的高度，例如像上面的B3，它的高度是3 =================================以下是combine======================= 將兩個binomial heap化成一個binomial heap step1:將兩個binomail heap按照degree大小由小而大來排列 例: heap1─12─ 1 ─── 7 heap2─18— 3 ────5 ︳ ╱︳ ︳ ╱︱╲ 　　　　　　　　　23 13 15　　　　 37 30 10 44 │ ╱︳ ︱ 19 40 31 28 ︱ 50 ==>heap ─12—18─── 1 ── 3 ─── 7 ───── 5 ︳ ︳ ╱︳ ╱︱╲ 23 37 13 15 30 10 44 ︳ ╱︳ ︳ 19 40 31 28 ︳ 50 □代表degree0 □代表degree1 □代表degree2 □代表degree3 step2:將degree合併較小的degree 較小的數值放在上面 所以上面的結果變成以下 先合併degree 0的 ==>heap ─ 12 ─── 1 ── 3 ─── 7 ───── 5 │ ︳ ︳ ╱︳ ╱︱╲ 18 23 37 13 15 30 10 44 ︳ ╱︳ ︳ 19 40 31 28 ︳ 50 在合併degreee1的(記得數字小的放上面) ==>heap ─ 12 ─── 1 ── 7 ───── 5 │ ╱︳ ╱︳ ╱︱╲ 18 3 23 13 15 30 10 44 ︳ ︳ ╱︳ ︳ 37 19 40 31 28 ︳ 50 合併degree2的 ==>heap ─ 12 ─── 1 ───── 5 │ ╱︳╲ ╱︱╲ 18 7 3 23 30 10 44 ╱︳ ︳ ╱︳ ︳ 13 15 37 40 31 28 ︱ ︳ 19 50 最後合併degree3的 ==>heap ─ 12 ───── 1 │ ╱︳﹨╲ 18 ╱ ︳ ﹨ ╲ ╱ ︳ ﹨ ╲ 5 7 3 23 ╱︳╲ ︱﹨ ︳ 30 10 44 13 15 37 ╱︳︱ ︱ 40 31 28 19 ︱ 50 =================================以下為insert============================ 這個就有點像是combine了 反正就是先插入節點(18) 然後執行合併 heap1─12─ 1 ─── 7─18 ︳ ╱︳ 　　　　　　　　　23 13 15　　　　 │ 19 ↓ heap1─12 ─ 1 ─── 7 ︱ ︳ ╱︳ 　　　　　18　 23 13 15　　　　 │ 19 ==============================最後是del min========================== 刪除最小值後會分成好幾個heap，最後在執行合併 heap ─ 12 ── 1 ────7 ╱︳ ╱︱╲ 10 23 5 13 15 │ ╱︳ ︱ 16 11 17 19 ︱ 28 刪除1以後變成兩顆heap heap ─ 12 ──10──23 ────7 ︱ ╱︱╲ 16 5 13 15 ╱︳ ︱ 11 17 19 ︱ 28 執行合併 heap ─ 12 ──10───7 ︱ ︱ ╱︱╲ 23 16 5 13 15 ╱︳ ︱ 11 17 19 ︱ 28 ↓ heap ──10──────7 ╱︳ ╱︱╲ 12 16 5 13 15 ︱ ╱︳ ︱ 23 11 17 19 ︱ 28 感謝你耐心看完 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.246.46 ※ 編輯: whisp1222 來自: 211.74.246.46 (04/30 17:55)