其中fib_heap_consolidate(heap)的作用是合并斐波那契堆的根链表中相同度数的树，它的相关代码如下：
 view sourceprint?
01.1 /*
02.2 * 将node链接到root根结点
03.3 */
04.4 static void fib_heap_link(FibHeap * heap, FibNode * node, FibNode *root)
05.5 {
06.6 // 将node从双链表中移除
07.7 fib_node_remove(node);
08.8 // 将node设为root的孩子
09.9 if (root->child == NULL)
10.10 root->child = node;
11.11 else
12.12 fib_node_add(node, root->child);
13.13
14.14 node->parent = root;
15.15 root->degree++;
16.16 node->marked = 0;
17.17 }
18.18
19.19 /*
20.20 * 创建fib_heap_consolidate所需空间
21.21 */
22.22 static void fib_heap_cons_make(FibHeap * heap)
23.23 {
24.24 int old = heap->maxDegree;
25.25
26.26 // 计算log2(x)，'+1'意味着向上取整！
27.27 // ex. log2(13) = 3，向上取整为3+1=4。
28.28 heap->maxDegree = LOG2(heap->keyNum) + 1;
29.29
30.30 // 如果原本空间不够，则再次分配内存
31.31 if (old >= heap->maxDegree)
32.32 return ;
33.33
34.34 // 因为度为heap->maxDegree可能被合并，所以要maxDegree+1
35.35 heap->cons = (FibNode **)realloc(heap->cons,
36.36 sizeof(FibHeap *) * (heap->maxDegree + 1));
37.37 }
38.38
39.39 /*
40.40 * 合并斐波那契堆的根链表中左右相同度数的树
41.41 */
42.42 static void fib_heap_consolidate(FibHeap *heap)
43.43 {
44.44 int i, d, D;
45.45 FibNode *x, *y, *tmp;
46.46
47.47 fib_heap_cons_make(heap);//开辟哈希所用空间
48.48 D = heap->maxDegree + 1;
49.49
50.50 for (i = 0; i < D; i++)
51.51 heap->cons = NULL;
52.52
53.53 // 合并相同度的根节点，使每个度数的树唯一
54.54 while (heap->min != NULL)
55.55 {
56.56 x = fib_heap_remove_min(heap); // 取出堆中的最小树(最小节点所在的树)
57.57 d = x->degree; // 获取最小树的度数
58.58 // heap->cons[d] != NULL，意味着有两棵树(x和y)的'度数'相同。
59.59 while (heap->cons[d] != NULL)
60.60 {
61.61 y = heap->cons[d]; // y是'与x的度数相同的树'
62.62 if (x->key > y->key) // 保证x的键值比y小
63.63 {
64.64 tmp = x;
65.65 x = y;
66.66 y = tmp;
67.67
68.68 }
69.69 fib_heap_link(heap, y, x); // 将y链接到x中
70.70 heap->cons[d] = NULL;
71.71 d++;
72.72 }
73.73 heap->cons[d] = x;
74.74 }
75.75 heap->min = NULL;
76.76
77.77 // 将heap->cons中的结点重新加到根表中
78.78 for (i=0; i<D; i++)
79.79 {
80.80 if (heap->cons != NULL)
81.81 {
82.82 if (heap->min == NULL)
83.83 heap->min = heap->cons;
84.84 else
85.85 {
86.86 fib_node_add(heap->cons, heap->min);
87.87 if ((heap->cons)->key < heap->min->key)
88.88 heap->min = heap->cons;
89.89 }
90.90 }
91.91 }
92.92 }
5. 减小节点值
减少斐波那契堆中的节点的键值，这个操作的难点是：如果减少节点后破坏了'最小堆'性质，如何去维护呢？下面对一般性情况进行分析。
(1) 首先，将'被减小节点'从'它所在的最小堆'剥离出来；然后将'该节点'关联到'根链表'中。 倘若被减小的节点不是单独一个节点，而是包含子树的树根。则是将以'被减小节点'为根的子树从'最小堆'中剥离出来，然后将该树关联到根链表中。
(2) 接着，对'被减少节点'的原父节点进行'级联剪切'。所谓'级联剪切'，就是在被减小节点破坏了最小堆性质，并被切下来之后；再从'它的父节点'进行递归级联剪切操作。
而级联操作的具体动作则是：若父节点(被减小节点的父节点)的marked标记为false，则将其设为true，然后退出。
否则，将父节点从最小堆中切下来(方式和'切被减小节点的方式'一样)；然后递归对祖父节点进行'级联剪切'。
marked标记的作用就是用来标记'该节点的子节点是否有被删除过'，它的作用是来实现级联剪切。而级联剪切的真正目的是为了防止'最小堆'由二叉树演化成链表。
(3) 最后，别忘了对根链表的最小节点进行更新。 |
