定义:由一些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)