4 public void insert(T key) {
5 BinomialNode node;
6
7 // 禁止插入相同的键值
8 if (contains(key)==true) {
9 System.out.printf("insert failed: the key(%s) is existed already!\n", key);
10 return ;
11 }
12
13 node = new BinomialNode(key);
14 if (node==null)
15 return ;
16
17 mRoot = union(mRoot, node);
18 }
复制代码
在插入时，首先通过contains(key)查找键值为key的节点。存在的话，则直接返回；不存在的话，则新建BinomialNode对象node，然后将node和heap进行合并。
注意：我这里实现的二项堆是"进制插入相同节点的"！若你想允许插入相同键值的节点，则屏蔽掉插入操作中的contains(key)部分代码即可。
4. 删除操作
删除二项堆中的某个节点，需要的步骤概括起来如下：
(01) 将"该节点"交换到"它所在二项树"的根节点位置。方法是，从"该节点"不断向上(即向树根方向)"遍历，不断交换父节点和子节点的数据，直到被删除的键值到达树根位置。
(02) 将"该节点所在的二项树"从二项堆中移除；将该二项堆记为heap。
(03) 将"该节点所在的二项树"进行反转。反转的意思，就是将根的所有孩子独立出来，并将这些孩子整合成二项堆，将该二项堆记为child。
(04) 将child和heap进行合并操作。
下面，先看看删除操作的代码；再进行图文说明。
删除操作代码(Java)
复制代码
1 /*
2 * 删除节点：删除键值为key的节点
3 */
4 private BinomialNode remove(BinomialNode root, T key) {
5 if (root==null)
6 return root;
7
8 BinomialNode node;
9
10 // 查找键值为key的节点
11 if ((node = search(root, key)) == null)
12 return root;
13
14 // 将被删除的节点的数据数据上移到它所在的二项树的根节点
15 BinomialNode parent = node.parent;
16 while (parent != null) {
17 // 交换数据
18 T tmp = node.key;
19 node.key = parent.key;
20 parent.key = tmp;
21
22 // 下一个父节点
23 node = parent;
24 parent = node.parent;
25 }
26
27 // 找到node的前一个根节点(prev)
28 BinomialNode prev = null;
29 BinomialNode pos = root;
30 while (pos != node) {
31 prev = pos;
32 pos = pos.next;
33 }
34 // 移除node节点
35 if (prev!=null)
36 prev.next = node.next;
37 else
38 root = node.next;
39
40 root = union(root, reverse(node.child));
41
42 // help GC
43 node = null;
44
45 return root;
46 }
47
48 public void remove(T key) {
49 mRoot = remove(mRoot, key);
50 }
复制代码
remove(key)的作用是删除二项堆中键值为key的节点，并返回删除节点后的二项堆。
下面通过示意图来对删除操作进行说明(删除二项堆中的节点20)。
总的思想，就是将被"删除节点"从它所在的二项树中孤立出来，然后再对二项树进行相应的处理。
PS. 删除操作的图文解析过程与"测试程序(Main.java)中的testDelete()函数"是对应的！
5. 更新操作
更新二项堆中的某个节点，就是修改节点的值，它包括两部分分："减少节点的值" 和 "增加节点的值" 。
更新操作代码(Java)
复制代码
/*
* 更新二项堆的节点node的键值为key
*/
private void updateKey(BinomialNode node, T key) {
if (node == null)
return ;
int cmp = key.compareTo(node.key);
if(cmp < 0) // key < node.key
decreaseKey(node, key);
else if(cmp > 0) // key > node.key
increaseKey(node, key);
else
System.out.println("No need to update!!!");
}
/*
* 将二项堆中键值oldkey更新为newkey
*/
public void update(T oldkey, T newkey) {
BinomialNode node;
node = search(mRoot, oldkey);
if (node != null)
updateKey(node, newkey);
}
复制代码
5.1 减少节点的值
减少节点值的操作很简单：该节点一定位于一棵二项树中，减小"二项树"中某个节点的值后要保证"该二项树仍然是一个最小堆"；因此，就需要我们不断的将该节点上调。
减少操作代码(Java)
复制代码
1 /*
2 * 减少关键字的值：将二项堆中的节点node的键值减小为key。
3 */
4 private void decreaseKey(BinomialNode node, T key) {
5 if(key.compareTo(node.key)>=0 || contains(key)==true) {
6 System.out.println("decre