二项树的介绍
二项树的定义
二项堆是二项树的集合。在了解二项堆之前&＃xff0c;先对二项树进行介绍。
二项树是一种递归定义的有序树。它的递归定义如下&＃xff1a;
(01) 二项树B0只有一个结点&＃xff1b;
(02) 二项树Bk由两棵二项树B(k-1)组成的&＃xff0c;其中一棵树是另一棵树根的最左孩子。
如下图所示&＃xff1a;
上图的B0、B1、B2、B3、B4都是二项树。对比前面提到的二项树的定义&＃xff1a;B0只有一个节点&＃xff0c;B1由两个B0所组成&＃xff0c;B2由两个B1所组成&＃xff0c;B3由两个B2所组成&＃xff0c;B4由两个B3所组成&＃xff1b;而且&＃xff0c;当两颗相同的二项树组成另一棵树时&＃xff0c;其中一棵树是另一棵树的最左孩子。
二项树的性质
二项树有以下性质&＃xff1a;
[性质一] Bk共有2k个节点。
如上图所示&＃xff0c;B0有20&＃61;1节点&＃xff0c;B1有21&＃61;2个节点&＃xff0c;B2有22&＃61;4个节点&＃xff0c;...
[性质二] Bk的高度为k。
如上图所示&＃xff0c;B0的高度为0&＃xff0c;B1的高度为1&＃xff0c;B2的高度为2&＃xff0c;...
[性质三] Bk在深度i处恰好有C(k,i)个节点&＃xff0c;其中i&＃61;0,1,2,...,k。
C(k,i)是高中数学中阶乘元素&＃xff0c;例如&＃xff0c;C(10,3)&＃61;(10*9*8) / (3*2*1)&＃61;240
B4中深度为0的节点C(4,0)&＃61;1
B4中深度为1的节点C(4,1)&＃61; 4 / 1 &＃61; 4
B4中深度为2的节点C(4,2)&＃61; (4*3) / (2*1) &＃61; 6
B4中深度为3的节点C(4,3)&＃61; (4*3*2) / (3*2*1) &＃61; 4
B4中深度为4的节点C(4,4)&＃61; (4*3*2*1) / (4*3*2*1) &＃61; 1
合计得到B4的节点分布是(1,4,6,4,1)。
[性质四] 根的度数为k&＃xff0c;它大于任何其它节点的度数。
节点的度数是该结点拥有的子树的数目。
注意&＃xff1a;树的高度和深度是相同的。关于树的高度的概念&＃xff0c;《算法导论》中只有一个节点的树的高度是0&＃xff0c;而"维基百科"中只有一个节点的树的高度是1。本文使用了《算法导论中》"树的高度和深度"的概念。
二项堆的介绍
二项堆和之前所讲的堆(二叉堆、左倾堆、斜堆)一样&＃xff0c;也是用于实现优先队列的。二项堆是指满足以下性质的二项树的集合&＃xff1a;
(01) 每棵二项树都满足最小堆性质。即&＃xff0c;父节点的关键字 <&＃61; 它的孩子的关键字。
(02) 不能有两棵或以上的二项树具有相同的度数(包括度数为0)。换句话说&＃xff0c;具有度数k的二项树有0个或1个。
上图就是一棵二项堆&＃xff0c;它由二项树B0、B2和B3组成。对比二项堆的定义&＃xff1a;(01)二项树B0、B2、B3都是最小堆&＃xff1b;(02)二项堆不包含相同度数的二项树。
二项堆的第(01)个性质保证了二项堆的最小节点就是某个二项树的根节点&＃xff0c;第(02)个性质则说明结点数为n的二项堆最多只有log{n} &＃43; 1棵二项树。实际上&＃xff0c;将包含n个节点的二项堆&＃xff0c;表示成若干个2的指数和(或者转换成二进制)&＃xff0c;则每一个2个指数都对应一棵二项树。例如&＃xff0c;13(二进制是1101)的2个指数和为13&＃61;23 &＃43; 22&＃43; 20, 因此具有13个节点的二项堆由度数为3, 2, 0的三棵二项树组成。
二项堆的基本操作
二项堆是可合并堆&＃xff0c;它的合并操作的复杂度是O(log n)。
1. 基本定义
public class BinomialHeap where T : IComparable{private BinomialNode mRoot; // 根结点private class BinomialNode where T : IComparable{public T key; // 关键字(键值)public int degree; // 度数public BinomialNode child; // 左孩子public BinomialNode parent; // 父节点public BinomialNode next; // 兄弟节点public BinomialNode(T key){this.key &＃61; key;this.degree &＃61; 0;this.child &＃61; null;this.parent &＃61; null;this.next &＃61; null;}public override string ToString(){return "key:" &＃43; key;}}}
BinomialNode是二项堆的节点。它包括了关键字(key)&＃xff0c;用于比较节点大小&＃xff1b;度数(degree)&＃xff0c;用来表示当前节点的度数&＃xff1b;左孩子(child)、父节点(parent)以及兄弟节点(next)。
BinomialHeap是二项堆对应的类&＃xff0c;它包括了二项堆的根节点mRoot以及二项堆的基本操作的定义。
下面是一棵二项堆的树形图和它对应的内存结构关系图。
2. 合并操作
合并操作是二项堆的重点&＃xff0c;它的添加操作也是基于合并操作来实现的。合并两个二项堆&＃xff0c;需要的步骤概括起来如下&＃xff1a;
(01) 将两个二项堆的根链表合并成一个链表。合并后的新链表按照"节点的度数"单调递增排列。
(02) 将新链表中"根节点度数相同的二项树"连接起来&＃xff0c;直到所有根节点度数都不相同。
下面&＃xff0c;先看看合并操作的代码&＃xff1b;然后再通过示意图对合并操作进行说明。
merge()代码
/** 将h1, h2中的根表合并成一个按度数递增的链表&＃xff0c;返回合并后的根节点*/private BinomialNode merge(BinomialNode h1, BinomialNode h2){if (h1 &＃61;&＃61; null) return h2;if (h2 &＃61;&＃61; null) return h1;// root是新堆的根&＃xff0c;h3用来遍历h1和h3的。BinomialNode pre_h3, h3, root &＃61; null;pre_h3 &＃61; null;//整个while&＃xff0c;h1, h2, pre_h3, h3都在往后顺移while ((h1 !&＃61; null) && (h2 !&＃61; null)){if (h1.degree <&＃61; h2.degree){h3 &＃61; h1;h1 &＃61; h1.next;}else{h3 &＃61; h2;h2 &＃61; h2.next;}if (pre_h3 &＃61;&＃61; null){pre_h3 &＃61; h3;root &＃61; h3;}else{pre_h3.next &＃61; h3;pre_h3 &＃61; h3;}if (h1 !&＃61; null){h3.next &＃61; h1;}else{h3.next &＃61; h2;}}return root;}
link()代码
/** 合并两个二项堆&＃xff1a;将child合并到root中*/private void link(BinomialNode child, BinomialNode root){child.parent &＃61; root;child.next &＃61; root.child;root.child &＃61; child;root.degree&＃43;&＃43;;}
合并操作代码
/** 合并二项堆&＃xff1a;将h1, h2合并成一个堆&＃xff0c;并返回合并后的堆*/private BinomialNode union(BinomialNode h1, BinomialNode h2){BinomialNode root;// 将h1, h2中的根表合并成一个按度数递增的链表rootroot &＃61; merge(h1, h2);if (root &＃61;&＃61; null)return null;BinomialNode prev_x &＃61; null;BinomialNode x &＃61; root;BinomialNode next_x &＃61; x.next;while (next_x !&＃61; null){if ((x.degree !&＃61; next_x.degree)|| ((next_x.next !&＃61; null) && (next_x.degree &＃61;&＃61; next_x.next.degree))){// Case 1: x.degree !&＃61; next_x.degree// Case 2: x.degree &＃61;&＃61; next_x.degree &＃61;&＃61; next_x.next.degreeprev_x &＃61; x;x &＃61; next_x;}else if (x.key.CompareTo(next_x.key) <&＃61; 0){// Case 3: x.degree &＃61;&＃61; next_x.degree !&＃61; next_x.next.degree// && x.key <&＃61; next_x.keyx.next &＃61; next_x.next;link(next_x, x);}else{// Case 4: x.degree &＃61;&＃61; next_x.degree !&＃61; next_x.next.degree// && x.key > next_x.keyif (prev_x &＃61;&＃61; null){root &＃61; next_x;}else{prev_x.next &＃61; next_x;}link(x, next_x);x &＃61; next_x;}next_x &＃61; x.next;}return root;}/** 将二项堆other合并到当前堆中*/public void union(BinomialHeap other){if (other !&＃61; null && other.mRoot !&＃61; null)mRoot &＃61; union(mRoot, other.mRoot);}
合并函数combine(h1, h2)的作用是将h1和h2合并&＃xff0c;并返回合并后的二项堆。在combine(h1, h2)中&＃xff0c;涉及到了两个函数merge(h1, h2)和link(child, root)。
merge(h1, h2)就是我们前面所说的"两个二项堆的根链表合并成一个链表&＃xff0c;合并后的新链表按照&＃39;节点的度数&＃39;单调递增排序"。
link(child, root)则是为了合并操作的辅助函数&＃xff0c;它的作用是将"二项堆child的根节点"设为"二项堆root的左孩子"&＃xff0c;从而将child整合到root中去。
在combine(h1, h2)中对h1和h2进行合并时&＃xff1b;首先通过 merge(h1, h2) 将h1和h2的根链表合并成一个"按节点的度数单调递增"的链表&＃xff1b;然后进入while循环&＃xff0c;对合并得到的新链表进行遍历&＃xff0c;将新链表中"根节点度数相同的二项树"连接起来&＃xff0c;直到所有根节点度数都不相同为止。在将新联表中"根节点度数相同的二项树"连接起来时&＃xff0c;可以将被连接的情况概括为4种。
x是根链表的当前节点&＃xff0c;next_x是x的下一个(兄弟)节点。
Case 1: x->degree !&＃61; next_x->degree
即&＃xff0c;"当前节点的度数"与"下一个节点的度数"相等时。此时&＃xff0c;不需要执行任何操作&＃xff0c;继续查看后面的节点。
Case 2: x->degree &＃61;&＃61; next_x->degree &＃61;&＃61; next_x->next->degree
即&＃xff0c;"当前节点的度数"、"下一个节点的度数"和"下下一个节点的度数"都相等时。此时&＃xff0c;暂时不执行任何操作&＃xff0c;还是继续查看后面的节点。实际上&＃xff0c;这里是将"下一个节点"和"下下一个节点"等到后面再进行整合连接。
Case 3: x->degree &＃61;&＃61; next_x->degree !&＃61; next_x->next->degree
&& x->key <&＃61; next_x->key
即&＃xff0c;"当前节点的度数"与"下一个节点的度数"相等&＃xff0c;并且"当前节点的键值"<&＃61;"下一个节点的度数"。此时&＃xff0c;将"下一个节点(对应的二项树)"作为"当前节点(对应的二项树)的左孩子"。
Case 4: x->degree &＃61;&＃61; next_x->degree !&＃61; next_x->next->degree
&& x->key > next_x->key
即&＃xff0c;"当前节点的度数"与"下一个节点的度数"相等&＃xff0c;并且"当前节点的键值">"下一个节点的度数"。此时&＃xff0c;将"当前节点(对应的二项树)"作为"下一个节点(对应的二项树)的左孩子"。
下面通过示意图来对合并操作进行说明。
第1步&＃xff1a;将两个二项堆的根链表合并成一个链表
执行完第1步之后&＃xff0c;得到的新链表中有许多度数相同的二项树。实际上&＃xff0c;此时得到的是对应"Case 4"的情况&＃xff0c;"树41"(根节点为41的二项树)和"树13"的度数相同&＃xff0c;且"树41"的键值 > "树13"的键值。此时&＃xff0c;将"树41"作为"树13"的左孩子。
第2步&＃xff1a;合并"树41"和"树13"
执行完第2步之后&＃xff0c;得到的是对应"Case 3"的情况&＃xff0c;"树13"和"树28"的度数相同&＃xff0c;且"树13"的键值 <"树28"的键值。此时&＃xff0c;将"树28"作为"树13"的左孩子。
第3步&＃xff1a;合并"树13"和"树28"
执行完第3步之后&＃xff0c;得到的是对应"Case 2"的情况&＃xff0c;"树13"、"树28"和"树7"这3棵树的度数都相同。此时&＃xff0c;将x设为下一个节点。
第4步&＃xff1a;将x和next_x往后移
执行完第4步之后&＃xff0c;得到的是对应"Case 3"的情况&＃xff0c;"树7"和"树11"的度数相同&＃xff0c;且"树7"的键值 <"树11"的键值。此时&＃xff0c;将"树11"作为"树7"的左孩子。
第5步&＃xff1a;合并"树7"和"树11"
执行完第5步之后&＃xff0c;得到的是对应"Case 4"的情况&＃xff0c;"树7"和"树6"的度数相同&＃xff0c;且"树7"的键值 > "树6"的键值。此时&＃xff0c;将"树7"作为"树6"的左孩子。
第6步&＃xff1a;合并"树7"和"树6"
此时&＃xff0c;合并操作完成&＃xff01;
PS. 合并操作的图文解析过程与"测试程序中的testUnion()函数"是对应的&＃xff01;
3. 插入操作
理解了"合并"操作之后&＃xff0c;插入操作就相当简单了。插入操作可以看作是将"要插入的节点"和当前已有的堆进行合并。
插入操作代码
/** 新建key对应的节点&＃xff0c;并将其插入到二项堆中。*/public void insert(T key){BinomialNode node;// 禁止插入相同的键值if (contains(key) &＃61;&＃61; true){Console.WriteLine("insert failed: the key({0}) is existed already!\n", key);return;}node &＃61; new BinomialNode(key);if (node &＃61;&＃61; null)return;mRoot &＃61; union(mRoot, node);}
在插入时&＃xff0c;首先通过contains(key)查找键值为key的节点。存在的话&＃xff0c;则直接返回&＃xff1b;不存在的话&＃xff0c;则新建BinomialNode对象node&＃xff0c;然后将node和heap进行合并。
注意&＃xff1a;我这里实现的二项堆是"进制插入相同节点的"&＃xff01;若你想允许插入相同键值的节点&＃xff0c;则屏蔽掉插入操作中的contains(key)部分代码即可。
4. 删除操作
删除二项堆中的某个节点&＃xff0c;需要的步骤概括起来如下&＃xff1a;
(01) 将"该节点"交换到"它所在二项树"的根节点位置。方法是&＃xff0c;从"该节点"不断向上(即向树根方向)"遍历&＃xff0c;不断交换父节点和子节点的数据&＃xff0c;直到被删除的键值到达树根位置。
(02) 将"该节点所在的二项树"从二项堆中移除&＃xff1b;将该二项堆记为heap。
(03) 将"该节点所在的二项树"进行反转。反转的意思&＃xff0c;就是将根的所有孩子独立出来&＃xff0c;并将这些孩子整合成二项堆&＃xff0c;将该二项堆记为child。
(04) 将child和heap进行合并操作。
下面&＃xff0c;先看看删除操作的代码&＃xff1b;再进行图文说明。
删除操作代码
/* * 删除节点&＃xff1a;删除键值为key的节点*/private BinomialNode remove(BinomialNode root, T key){if (root &＃61;&＃61; null)return root;BinomialNode node;// 查找键值为key的节点if ((node &＃61; search(root, key)) &＃61;&＃61; null)return root;// 将被删除的节点的数据数据上移到它所在的二项树的根节点BinomialNode parent &＃61; node.parent;while (parent !&＃61; null){// 交换数据T tmp &＃61; node.key;node.key &＃61; parent.key;parent.key &＃61; tmp;// 下一个父节点node &＃61; parent;parent &＃61; node.parent;}// 找到node的前一个根节点(prev)BinomialNode prev &＃61; null;BinomialNode pos &＃61; root;while (pos !&＃61; node){prev &＃61; pos;pos &＃61; pos.next;}// 移除node节点if (prev !&＃61; null)prev.next &＃61; node.next;elseroot &＃61; node.next;root &＃61; union(root, reverse(node.child));// help GCnode &＃61; null;return root;}public void remove(T key){mRoot &＃61; remove(mRoot, key);}
remove(key)的作用是删除二项堆中键值为key的节点&＃xff0c;并返回删除节点后的二项堆。
下面通过示意图来对删除操作进行说明(删除二项堆中的节点20)。
总的思想&＃xff0c;就是将被"删除节点"从它所在的二项树中孤立出来&＃xff0c;然后再对二项树进行相应的处理。
PS. 删除操作的图文解析过程与"测试程序中的testDelete()函数"是对应的&＃xff01;
5. 更新操作
更新二项堆中的某个节点&＃xff0c;就是修改节点的值&＃xff0c;它包括两部分分&＃xff1a;"减少节点的值" 和 "增加节点的值" 。
更新操作代码
/* * 更新二项堆的节点node的键值为key*/private void updateKey(BinomialNode node, T key){if (node &＃61;&＃61; null)return;int cmp &＃61; key.CompareTo(node.key);if (cmp <0) // key
decreaseKey(node, key);else if (cmp > 0) // key > node.key
increaseKey(node, key);elseConsole.WriteLine("No need to update!!!");}/* * 将二项堆中键值oldkey更新为newkey*/public void update(T oldkey, T newkey){BinomialNode node;node &＃61; search(mRoot, oldkey);if (node !&＃61; null)updateKey(node, newkey);}
5.1 减少节点的值
减少节点值的操作很简单&＃xff1a;该节点一定位于一棵二项树中&＃xff0c;减小"二项树"中某个节点的值后要保证"该二项树仍然是一个最小堆"&＃xff1b;因此&＃xff0c;就需要我们不断的将该节点上调。
减少操作代码
/* * 减少关键字的值&＃xff1a;将二项堆中的节点node的键值减小为key。*/private void decreaseKey(BinomialNode node, T key){if (key.CompareTo(node.key) >&＃61; 0 || contains(key) &＃61;&＃61; true){Console.WriteLine("decrease failed: the new key(" &＃43; key &＃43; ") is existed already, or is no smaller than current key(" &＃43; node.key &＃43; ")");return;}node.key &＃61; key;BinomialNode child, parent;child &＃61; node;parent &＃61; node.parent;while (parent !&＃61; null && child.key.CompareTo(parent.key) <0){// 交换parent和child的数据T tmp &＃61; parent.key;parent.key &＃61; child.key;child.key &＃61; tmp;child &＃61; parent;parent &＃61; child.parent;}}
下面是减少操作的示意图(20->2)
减少操作的思想很简单&＃xff0c;就是"保持被减节点所在二项树的最小堆性质"。
PS. 减少操作的图文解析过程与"测试程序中的testDecrease()函数"是对应的&＃xff01;
5.2 增加节点的值
增加节点值的操作也很简单。上面说过减少要将被减少的节点不断上调&＃xff0c;从而保证"被减少节点所在的二项树"的最小堆性质&＃xff1b;而增加操作则是将被增加节点不断的下调&＃xff0c;从而保证"被增加节点所在的二项树"的最小堆性质。
增加操作代码
/* * 增加关键字的值&＃xff1a;将二项堆中的节点node的键值增加为key。*/private void increaseKey(BinomialNode node, T key){if (key.CompareTo(node.key) <&＃61; 0 || contains(key) &＃61;&＃61; true){Console.WriteLine("increase failed: the new key(" &＃43; key &＃43; ") is existed already, or is no greater than current key(" &＃43; node.key &＃43; ")");return;}node.key &＃61; key;BinomialNode cur &＃61; node;BinomialNode child &＃61; cur.child;while (child !&＃61; null){if (cur.key.CompareTo(child.key) > 0){// 如果"当前节点" <"它的左孩子"&＃xff0c;// 则在"它的孩子中(左孩子 和 左孩子的兄弟)"中&＃xff0c;找出最小的节点&＃xff1b;// 然后将"最小节点的值" 和 "当前节点的值"进行互换BinomialNode least &＃61; child; // least是child和它的兄弟中的最小节点while (child.next !&＃61; null){if (least.key.CompareTo(child.next.key) > 0)least &＃61; child.next;child &＃61; child.next;}// 交换最小节点和当前节点的值T tmp &＃61; least.key;least.key &＃61; cur.key;cur.key &＃61; tmp;// 交换数据之后&＃xff0c;再对"原最小节点"进行调整&＃xff0c;使它满足最小堆的性质&＃xff1a;父节点 <&＃61; 子节点cur &＃61; least;child &＃61; cur.child;}else{child &＃61; child.next;}}}
下面是增加操作的示意图(6->60)
增加操作的思想很简单&＃xff0c;"保持被增加点所在二项树的最小堆性质"。
PS. 增加操作的图文解析过程与"测试程序中的testIncrease()函数"是对应的&＃xff01;
注意&＃xff1a;关于二项堆的"查找"、"更新"、"打印"等接口就不再单独介绍了&＃xff0c;后文的源码中有给出它们的实现代码。有兴趣的话&＃xff0c;Please RTFSC(Read The Fucking Source Code)&＃xff01;
二项堆的实现(完整源码)
二项堆的实现文件
public class BinomialHeap where T : IComparable{private BinomialNode mRoot; // 根结点private class BinomialNode where T : IComparable{public T key; // 关键字(键值)public int degree; // 度数public BinomialNode child; // 左孩子public BinomialNode parent; // 父节点public BinomialNode next; // 兄弟节点public BinomialNode(T key){this.key &＃61; key;this.degree &＃61; 0;this.child &＃61; null;this.parent &＃61; null;this.next &＃61; null;}public override string ToString(){return "key:" &＃43; key;}}public BinomialHeap(){mRoot &＃61; null;}/** 获取二项堆中的最小节点的键值*/public T minimum(){if (mRoot &＃61;&＃61; null)return default(T);BinomialNode x, prev_x; // x是用来遍历的当前节点BinomialNode y, prev_y; // y是最小节点
prev_x &＃61; mRoot;x &＃61; mRoot.next;prev_y &＃61; null;y &＃61; mRoot;// 找到最小节点while (x !&＃61; null){if (x.key.CompareTo(y.key) <0){y &＃61; x;prev_y &＃61; prev_x;}prev_x &＃61; x;x &＃61; x.next;}return y.key;}/** 合并两个二项堆&＃xff1a;将child合并到root中*/private void link(BinomialNode child, BinomialNode root){child.parent &＃61; root;child.next &＃61; root.child;root.child &＃61; child;root.degree&＃43;&＃43;;}/** 将h1, h2中的根表合并成一个按度数递增的链表&＃xff0c;返回合并后的根节点*/private BinomialNode merge(BinomialNode h1, BinomialNode h2){if (h1 &＃61;&＃61; null) return h2;if (h2 &＃61;&＃61; null) return h1;// root是新堆的根&＃xff0c;h3用来遍历h1和h3的。BinomialNode pre_h3, h3, root &＃61; null;pre_h3 &＃61; null;//整个while&＃xff0c;h1, h2, pre_h3, h3都在往后顺移while ((h1 !&＃61; null) && (h2 !&＃61; null)){if (h1.degree <&＃61; h2.degree){h3 &＃61; h1;h1 &＃61; h1.next;}else{h3 &＃61; h2;h2 &＃61; h2.next;}if (pre_h3 &＃61;&＃61; null){pre_h3 &＃61; h3;root &＃61; h3;}else{pre_h3.next &＃61; h3;pre_h3 &＃61; h3;}if (h1 !&＃61; null){h3.next &＃61; h1;}else{h3.next &＃61; h2;}}return root;}/** 合并二项堆&＃xff1a;将h1, h2合并成一个堆&＃xff0c;并返回合并后的堆*/private BinomialNode union(BinomialNode h1, BinomialNode h2){BinomialNode root;// 将h1, h2中的根表合并成一个按度数递增的链表rootroot &＃61; merge(h1, h2);if (root &＃61;&＃61; null)return null;BinomialNode prev_x &＃61; null;BinomialNode x &＃61; root;BinomialNode next_x &＃61; x.next;while (next_x !&＃61; null){if ((x.degree !&＃61; next_x.degree)|| ((next_x.next !&＃61; null) && (next_x.degree &＃61;&＃61; next_x.next.degree))){// Case 1: x.degree !&＃61; next_x.degree// Case 2: x.degree &＃61;&＃61; next_x.degree &＃61;&＃61; next_x.next.degreeprev_x &＃61; x;x &＃61; next_x;}else if (x.key.CompareTo(next_x.key) <&＃61; 0){// Case 3: x.degree &＃61;&＃61; next_x.degree !&＃61; next_x.next.degree// && x.key <&＃61; next_x.keyx.next &＃61; next_x.next;link(next_x, x);}else{// Case 4: x.degree &＃61;&＃61; next_x.degree !&＃61; next_x.next.degree// && x.key > next_x.keyif (prev_x &＃61;&＃61; null){root &＃61; next_x;}else{prev_x.next &＃61; next_x;}link(x, next_x);x &＃61; next_x;}next_x &＃61; x.next;}return root;}/** 将二项堆other合并到当前堆中*/public void union(BinomialHeap other){if (other !&＃61; null && other.mRoot !&＃61; null)mRoot &＃61; union(mRoot, other.mRoot);}/** 新建key对应的节点&＃xff0c;并将其插入到二项堆中。*/public void insert(T key){BinomialNode node;// 禁止插入相同的键值if (contains(key) &＃61;&＃61; true){Console.WriteLine("insert failed: the key({0}) is existed already!\n", key);return;}node &＃61; new BinomialNode(key);if (node &＃61;&＃61; null)return;mRoot &＃61; union(mRoot, node);}/** 反转二项堆root&＃xff0c;并返回反转后的根节点*/private BinomialNode reverse(BinomialNode root){BinomialNode next;BinomialNode tail &＃61; null;if (root &＃61;&＃61; null)return root;root.parent &＃61; null;while (root.next !&＃61; null){next &＃61; root.next;root.next &＃61; tail;tail &＃61; root;root &＃61; next;root.parent &＃61; null;}root.next &＃61; tail;return root;}/** 移除二项堆root中的最小节点&＃xff0c;并返回删除节点后的二项树*/private BinomialNode extractMinimum(BinomialNode root){if (root &＃61;&＃61; null)return root;BinomialNode x, prev_x; // x是用来遍历的当前节点BinomialNode y, prev_y; // y是最小节点
prev_x &＃61; root;x &＃61; root.next;prev_y &＃61; null;y &＃61; root;// 找到最小节点while (x !&＃61; null){if (x.key.CompareTo(y.key) <0){y &＃61; x;prev_y &＃61; prev_x;}prev_x &＃61; x;x &＃61; x.next;}if (prev_y &＃61;&＃61; null) // root的根节点就是最小根节点root &＃61; root.next;else // root的根节点不是最小根节点prev_y.next &＃61; y.next;// 反转最小节点的左孩子&＃xff0c;得到最小堆child&＃xff1b;// 这样&＃xff0c;就使得最小节点所在二项树的孩子们都脱离出来成为一棵独立的二项树(不包括最小节点)BinomialNode child &＃61; reverse(y.child);// 将"删除最小节点的二项堆child"和"root"进行合并。root &＃61; union(root, child);// help GCy &＃61; null;return root;}public void extractMinimum(){mRoot &＃61; extractMinimum(mRoot);}/* * 减少关键字的值&＃xff1a;将二项堆中的节点node的键值减小为key。*/private void decreaseKey(BinomialNode node, T key){if (key.CompareTo(node.key) >&＃61; 0 || contains(key) &＃61;&＃61; true){Console.WriteLine("decrease failed: the new key(" &＃43; key &＃43; ") is existed already, or is no smaller than current key(" &＃43; node.key &＃43; ")");return;}node.key &＃61; key;BinomialNode child, parent;child &＃61; node;parent &＃61; node.parent;while (parent !&＃61; null && child.key.CompareTo(parent.key) <0){// 交换parent和child的数据T tmp &＃61; parent.key;parent.key &＃61; child.key;child.key &＃61; tmp;child &＃61; parent;parent &＃61; child.parent;}}/* * 增加关键字的值&＃xff1a;将二项堆中的节点node的键值增加为key。*/private void increaseKey(BinomialNode node, T key){if (key.CompareTo(node.key) <&＃61; 0 || contains(key) &＃61;&＃61; true){Console.WriteLine("increase failed: the new key(" &＃43; key &＃43; ") is existed already, or is no greater than current key(" &＃43; node.key &＃43; ")");return;}node.key &＃61; key;BinomialNode cur &＃61; node;BinomialNode child &＃61; cur.child;while (child !&＃61; null){if (cur.key.CompareTo(child.key) > 0){// 如果"当前节点" <"它的左孩子"&＃xff0c;// 则在"它的孩子中(左孩子 和 左孩子的兄弟)"中&＃xff0c;找出最小的节点&＃xff1b;// 然后将"最小节点的值" 和 "当前节点的值"进行互换BinomialNode least &＃61; child; // least是child和它的兄弟中的最小节点while (child.next !&＃61; null){if (least.key.CompareTo(child.next.key) > 0)least &＃61; child.next;child &＃61; child.next;}// 交换最小节点和当前节点的值T tmp &＃61; least.key;least.key &＃61; cur.key;cur.key &＃61; tmp;// 交换数据之后&＃xff0c;再对"原最小节点"进行调整&＃xff0c;使它满足最小堆的性质&＃xff1a;父节点 <&＃61; 子节点cur &＃61; least;child &＃61; cur.child;}else{child &＃61; child.next;}}}/* * 更新二项堆的节点node的键值为key*/private void updateKey(BinomialNode node, T key){if (node &＃61;&＃61; null)return;int cmp &＃61; key.CompareTo(node.key);if (cmp <0) // key
decreaseKey(node, key);else if (cmp > 0) // key > node.key
increaseKey(node, key);elseConsole.WriteLine("No need to update!!!");}/* * 将二项堆中键值oldkey更新为newkey*/public void update(T oldkey, T newkey){BinomialNode node;node &＃61; search(mRoot, oldkey);if (node !&＃61; null)updateKey(node, newkey);}/** 查找&＃xff1a;在二项堆中查找键值为key的节点*/private BinomialNode search(BinomialNode root, T key){BinomialNode child;BinomialNode parent &＃61; root;parent &＃61; root;while (parent !&＃61; null){if (parent.key.CompareTo(key) &＃61;&＃61; 0)return parent;else{if ((child &＃61; search(parent.child, key)) !&＃61; null)return child;parent &＃61; parent.next;}}return null;}/** 二项堆中是否包含键值key*/public bool contains(T key){return search(mRoot, key) !&＃61; null ? true : false;}/* * 删除节点&＃xff1a;删除键值为key的节点*/private BinomialNode remove(BinomialNode root, T key){if (root &＃61;&＃61; null)return root;BinomialNode node;// 查找键值为key的节点if ((node &＃61; search(root, key)) &＃61;&＃61; null)return root;// 将被删除的节点的数据数据上移到它所在的二项树的根节点BinomialNode parent &＃61; node.parent;while (parent !&＃61; null){// 交换数据T tmp &＃61; node.key;node.key &＃61; parent.key;parent.key &＃61; tmp;// 下一个父节点node &＃61; parent;parent &＃61; node.parent;}// 找到node的前一个根节点(prev)BinomialNode prev &＃61; null;BinomialNode pos &＃61; root;while (pos !&＃61; node){prev &＃61; pos;pos &＃61; pos.next;}// 移除node节点if (prev !&＃61; null)prev.next &＃61; node.next;elseroot &＃61; node.next;root &＃61; union(root, reverse(node.child));// help GCnode &＃61; null;return root;}public void remove(T key){mRoot &＃61; remove(mRoot, key);}/** 打印"二项堆"** 参数说明&＃xff1a;* node -- 当前节点* prev -- 当前节点的前一个节点(父节点or兄弟节点)* direction -- 1&＃xff0c;表示当前节点是一个左孩子;* 2&＃xff0c;表示当前节点是一个兄弟节点。*/private void print(BinomialNode node, BinomialNode prev, int direction){while (node !&＃61; null){if (direction &＃61;&＃61; 1) // node是根节点Console.WriteLine("\t{0}({1}) is {2}&＃39;s child\n", node.key, node.degree, prev.key);else // node是分支节点Console.WriteLine("\t{0}({1}) is {2}&＃39;s next\n", node.key, node.degree, prev.key);if (node.child !&＃61; null)print(node.child, node, 1);// 兄弟节点prev &＃61; node;node &＃61; node.next;direction &＃61; 2;}}public void print(){if (mRoot &＃61;&＃61; null)return;BinomialNode p &＃61; mRoot;Console.WriteLine("&＃61;&＃61; 二项堆( ");while (p !&＃61; null){Console.WriteLine("B{0} ", p.degree);p &＃61; p.next;}Console.WriteLine(")的详细信息&＃xff1a;\n");int i &＃61; 0;p &＃61; mRoot;while (p !&＃61; null){i&＃43;&＃43;;Console.WriteLine("{0}. 二项树B{1}: \n", i, p.degree);Console.WriteLine("\t{0}({1}) is root\n", p.key, p.degree);print(p.child, p, 1);p &＃61; p.next;}Console.WriteLine("\n");}}
二项堆的测试程序
public class TestBinomialHeap{private bool DEBUG &＃61; false;// 共7个 &＃61; 1&＃43;2&＃43;4private int[] a &＃61; { 12, 7, 25, 15, 28, 33, 41 };// 共13个 &＃61; 1&＃43;4&＃43;8private int[] b &＃61; {18, 35, 20, 42, 9,31, 23, 6, 48, 11,24, 52, 13 };// 验证"二项堆的插入操作"public void testInsert(){BinomialHeap<int> ha &＃61; new BinomialHeap<int>();// 二项堆haConsole.WriteLine("&＃61;&＃61; 二项堆(ha)中依次添加: ");for (int i &＃61; 0; i ){Console.Write("{0} ", a[i]);ha.insert(a[i]);}Console.WriteLine("\n");Console.WriteLine("&＃61;&＃61; 二项堆(ha)的详细信息: \n");ha.print();}// 验证"二项堆的合并操作"public void testUnion(){BinomialHeap<int> ha &＃61; new BinomialHeap<int>();BinomialHeap<int> hb &＃61; new BinomialHeap<int>();// 二项堆haConsole.WriteLine("&＃61;&＃61; 二项堆(ha)中依次添加: ");for (int i &＃61; 0; i ){Console.Write("{0} ", a[i]);ha.insert(a[i]);}Console.WriteLine("\n");Console.WriteLine("&＃61;&＃61; 二项堆(ha)的详细信息: \n");ha.print();// 二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)中依次添加: ");for (int i &＃61; 0; i ){Console.Write("{0} ", b[i]);hb.insert(b[i]);}Console.WriteLine("\n");// 打印二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)的详细信息: \n");hb.print();// 将"二项堆hb"合并到"二项堆ha"中。
ha.union(hb);// 打印二项堆ha的详细信息Console.WriteLine("&＃61;&＃61; 合并ha和hb后的详细信息:\n");ha.print();}// 验证"二项堆的删除操作"public void testDelete(){BinomialHeap<int> hb &＃61; new BinomialHeap<int>();// 二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)中依次添加: ");for (int i &＃61; 0; i ){Console.Write("{0} ", b[i]);hb.insert(b[i]);}Console.WriteLine("\n");// 打印二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)的详细信息: \n");hb.print();// 将"二项堆hb"合并到"二项堆ha"中。hb.remove(20);Console.WriteLine("&＃61;&＃61; 删除节点20后的详细信息: \n");hb.print();}// 验证"二项堆的更新(减少)操作"public void testDecrease(){BinomialHeap<int> hb &＃61; new BinomialHeap<int>();// 二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)中依次添加: ");for (int i &＃61; 0; i ){Console.Write("{0} ", b[i]);hb.insert(b[i]);}Console.WriteLine("\n");// 打印二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)的详细信息: \n");hb.print();// 将节点20更新为2hb.update(20, 2);Console.WriteLine("&＃61;&＃61; 更新节点20->2后的详细信息: \n");hb.print();}// 验证"二项堆的更新(减少)操作"public void testIncrease(){BinomialHeap<int> hb &＃61; new BinomialHeap<int>();// 二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)中依次添加: ");for (int i &＃61; 0; i ){Console.WriteLine("{0} ", b[i]);hb.insert(b[i]);}Console.WriteLine("\n");// 打印二项堆hbConsole.WriteLine("&＃61;&＃61; 二项堆(hb)的详细信息: \n");hb.print();// 将节点6更新为60hb.update(6, 60);Console.WriteLine("&＃61;&＃61; 更新节点6->60后的详细信息: \n");hb.print();}public void test(){// 1. 验证"二项堆的插入操作"
testInsert();// 2. 验证"二项堆的合并操作"
testUnion();// 3. 验证"二项堆的删除操作"
testDelete();// 4. 验证"二项堆的更新(减少)操作"
testDecrease();// 5. 验证"二项堆的更新(增加)操作"
testIncrease();}}
二项堆的测试程序
二项堆的测试程序包括了五部分&＃xff0c;分别是"插入"、"删除"、"增加"、"减少"、"合并"这5种功能的测试代码。默认是运行的"插入"功能代码&＃xff0c;你可以根据自己的需要来对相应的功能进行验证&＃xff01;
运行结果&＃xff1a;
&＃61;&＃61; 二项堆(ha)中依次添加: 12 7 25 15 28 33 41
&＃61;&＃61; 二项堆(ha)的详细信息:
&＃61;&＃61; 二项堆( B0 B1 B2 )的详细信息&＃xff1a;
1. 二项树B0: 41(0) is root
2. 二项树B1: 28(1) is root33(0) is 28&＃39;s child
3. 二项树B2: 7(2) is root15(1) is 7&＃39;s child25(0) is 15&＃39;s child12(0) is 15&＃39;s next
京公网安备 11010802041100号