二项堆(三)之 Java的实现(四)
ase failed: the new key("+key+") is existed already, or is no smaller than current key("+node.key+")");
7 return ;
8 }
9 node.key = key;
10
11 BinomialNode child, parent;
12 child = node;
13 parent = node.parent;
14 while(parent != null && child.key.compareTo(parent.key)<0) {
15 // 交换parent和child的数据
16 T tmp = parent.key;
17 parent.key = child.key;
18 child.key = tmp;
19
20 child = parent;
21 parent = child.parent;
22 }
23 }
复制代码
下面是减少操作的示意图(20->2)
减少操作的思想很简单，就是"保持被减节点所在二项树的最小堆性质"。
PS. 减少操作的图文解析过程与"测试程序(Main.java)中的testDecrease()函数"是对应的！
5.2 增加节点的值
增加节点值的操作也很简单。上面说过减少要将被减少的节点不断上调，从而保证"被减少节点所在的二项树"的最小堆性质；而增加操作则是将被增加节点不断的下调，从而保证"被增加节点所在的二项树"的最小堆性质。
增加操作代码(Java)
复制代码
1 /*
2 * 增加关键字的值：将二项堆中的节点node的键值增加为key。
3 */
4 private void increaseKey(BinomialNode node, T key) {
5 if(key.compareTo(node.key)<=0 || contains(key)==true) {
6 System.out.println("increase failed: the new key("+key+") is existed already, or is no greater than current key("+node.key+")");
7 return ;
8 }
9 node.key = key;
10
11 BinomialNode cur = node;
12 BinomialNode child = cur.child;
13 while (child != null) {
14
15 if(cur.key.compareTo(child.key) > 0) {
16 // 如果"当前节点" < "它的左孩子"，
17 // 则在"它的孩子中(左孩子 和 左孩子的兄弟)"中，找出最小的节点；
18 // 然后将"最小节点的值" 和 "当前节点的值"进行互换
19 BinomialNode least = child; // least是child和它的兄弟中的最小节点
20 while(child.next != null) {
21 if (least.key.compareTo(child.next.key) > 0)
22 least = child.next;
23 child = child.next;
24 }
25 // 交换最小节点和当前节点的值
26 T tmp = least.key;
27 least.key = cur.key;
28 cur.key = tmp;
29
30 // 交换数据之后，再对"原最小节点"进行调整，使它满足最小堆的性质：父节点 <= 子节点
31 cur = least;
32 child = cur.child;
33 } else {
34 child = child.next;
35 }
36 }
37 }
复制代码
下面是增加操作的示意图(6->60)
增加操作的思想很简单，"保持被增加点所在二项树的最小堆性质"。
PS. 增加操作的图文解析过程与"测试程序(Main.java)中的testIncrease()函数"是对应的！