→ bernachom:很清楚，前輩謝謝您，麻煩您寫這麼詳細的資料，感謝 04/30 18:19
定義:由一些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)