电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 斐波那契堆(一)之图文解析和C语言的实现（2） [打印本页]

作者: yuyang911220 时间: 2016-8-20 20:25 标题: 斐波那契堆(一)之图文解析和C语言的实现（2）

3. 合并操作
合并操作和插入操作的原理非常类似：将一个堆的根链表插入到另一个堆的根链表上即可。简单来说，就是将两个双链表拼接成一个双向链表。

上面是合并操作的示意图。该操作示意图与测试程序中的'合并操作'相对应！
合并操作代码
view source print ?

01./*
02.* 将双向链表b链接到双向链表a的后面
03.*
04.* 注意：此处a和b都是双向链表
05.*/
06.static void fib_node_cat(FibNode *a, FibNode *b)
07.{
08.FibNode *tmp;
09.

10.tmp          = a->right;
11.a->right    = b->right;
12.b->right->left = a;
13.b->right    = tmp;
14.tmp->left    = b;
15.}
16.

17./*
18.* 将h3, h4合并成一个堆，并返回合并后的堆
19.*/
20.FibHeap* fib_heap_union(FibHeap *h3, FibHeap *h4)
21.{
22.FibHeap *tmp;
23.

24.if (h3==NULL)
25.return h4;
26.if (h4==NULL)
27.return h3;
28.

29.// 以h3为'母'，将h4附加到h3上；下面是保证h3的度数大，尽可能的少操作。
30.if(h4->maxDegree > h3->maxDegree)
31.{
32.tmp = h3;
33.h3 = h4;
34.h4 = tmp;
35.}
36.

37.if((h3->min) == NULL)             // h3无'最小节点'
38.{
39.h3->min = h4->min;
40.h3->keyNum = h4->keyNum;
41.free(h4->cons);
42.free(h4);
43.}
44.else if((h4->min) == NULL)          // h3有'最小节点' && h4无'最小节点'
45.{
46.free(h4->cons);
47.free(h4);
48.}                                  // h3有'最小节点' && h4有'最小节点'
49.else
50.{
51.// 将'h4中根链表'添加到'h3'中
52.fib_node_cat(h3->min, h4->min);
53.if (h3->min->key > h4->min->key)
54.h3->min = h4->min;
55.h3->keyNum += h4->keyNum;
56.free(h4->cons);
57.free(h4);
58.}
59.

60.return h3;
61.}

4. 取出最小节点
抽取最小结点的操作是斐波那契堆中较复杂的操作。
(1）将要抽取最小结点的子树都直接串联在根表中；
(2）合并所有degree相等的树，直到没有相等的degree的树。

上面是取出最小节点的示意图。图中应该写的非常明白了，若有疑问，看代码。
此外，该操作示意图与测试程序中的'删除最小节点'相对应！有兴趣的可以亲自验证。
取出最小节点代码
view source print ?

01./*
02.* 移除最小节点，并返回移除节点后的斐波那契堆
03.*/
04.FibNode* _fib_heap_extract_min(FibHeap *heap)
05.{
06.if (heap==NULL || heap->min==NULL)
07.return NULL;
08.

09.FibNode *child = NULL;
10.FibNode *min = heap->min;
11.// 将min每一个儿子(儿子和儿子的兄弟)都添加到'斐波那契堆的根链表'中
12.while (min->child != NULL)
13.{
14.child = min->child;
15.fib_node_remove(child);
16.if (child->right == child)
17.min->child = NULL;
18.else
19.min->child = child->right;
20.

21.fib_node_add(child, heap->min);
22.child->parent = NULL;
23.}
24.

25.// 将min从根链表中移除
26.fib_node_remove(min);
27.// 若min是堆中唯一节点，则设置堆的最小节点为NULL；
28.// 否则，设置堆的最小节点为一个非空节点(min->right)，然后再进行调节。
29.if (min->right == min)
30.heap->min = NULL;
31.else
32.{
33.heap->min = min->right;
34.fib_heap_consolidate(heap);
35.}
36.heap->keyNum--;
37.

38.return min;
39.}

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)