﻿ 斐波那契堆 - 鸿网互联

斐波那契堆

```typedef struct FibonaciNode
{
int value;
int mark;
int num;
struct FibonaciNode *left;
struct FibonaciNode *right;
struct FibonaciNode *parent;
struct FibonaciNode *child;
} FibonaciNode;

typedef struct FibonaciHeap
{
FibonaciNode *min;
int num;
} FibonaciHeap;```

FibonaciNode中的mark属性记录结点的一些历史信息：

1.  斐波那契堆的初始化以及一些辅助操作

```// 初始化一个空的斐波那契堆
FibonaciHeap *initFibonaciHeap()
{
FibonaciHeap *heap = (FibonaciHeap *)malloc(sizeof(FibonaciHeap));
heap->min = NULL;
heap->num = 0;
return heap;
}```

```FibonaciNode *createFibonaciNode(int value)
{
FibonaciNode *node = (FibonaciNode *)malloc(sizeof(FibonaciNode));
node->child = NULL;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->value = value;
node->mark = NONE;
node->num = 0;
return node;
}```

```void destroyFibonaciHeap(FibonaciHeap **heap)
{
destroyFibonaciNode((*heap)->min);
(*heap)->min = NULL;
(*heap)->num = 0;
*heap = NULL;
}

void destroyFibonaciNode(FibonaciNode *node)
{
node->left->right = NULL;
while (node != NULL)
{
if (node->child != NULL)
{
destroyFibonaciNode(node->child);
}
FibonaciNode *del = node;
node = node->right;
free(del);
}
}```

2. 插入一个结点

```FibonaciNode *insertIntoFibonaciHeap(FibonaciHeap *heap, int value)
{
FibonaciNode *node = createFibonaciNode(value);
return insertIntoFibonaciHeap(heap, node);
}

FibonaciNode *insertIntoFibonaciHeap(FibonaciHeap *heap, FibonaciNode *node)
{
if (heap->min == NULL)
{
heap->min = node;
node->right = node;
node->left = node;
}
else
{
node->right = heap->min->right;
node->right->left = node;
heap->min->right = node;
node->left = heap->min;
if (node->value < heap->min->value)
{
heap->min = node;
}
}
heap->num++;
return node;
}```
上述代码先判断堆的根结点是否为空，是则直接以插入的新结点为in结点构造一个单元素的根链表，否则插入新结点到min结点的旁边，并更新堆的结点数。插入操作的时间复杂度为O(1)。

3. 提取最小结点

```// 将结点c作为孩子结点插入到结点p的孩子链表中
{
c->parent = p;
c->mark = FALSE;
p->num++;
if (p->child == NULL)
{
p->child = c;
c->left = c;
c->right = c;
return;
}
FibonaciNode *child = p->child;
c->right = child->right;
c->right->left = c;
child->right = c;
c->left = child;
}```

```// 提取最小结点
int extractMin(FibonaciHeap *heap)
{
if (heap->min == NULL)	return EMPTY_HEAP;

int mini = heap->min->value;
// 将最小结点的孩子结点插入到根链表中
FibonaciNode *child = heap->min->child;
if (child != NULL)
{
child->left->right = NULL;
while (child != NULL)
{
insertIntoFibonaciHeap(heap, child);
child = child->right;
}
}

// 删除最小结点
FibonaciNode *preMin = heap->min;
heap->min = preMin->right;
preMin->left->right = preMin->right;
preMin->right->left = preMin->left;
free(preMin);

heap->num--;
if (heap->num == 0)
{
// 堆为空
heap->min = NULL;
}
else
{
// 合并根链表中度数相同的结点
consolidate(heap);
}

return mini;
}```
extractMin方法返回min结点的值，并对堆进行调整。首先，调用insertIntoFibonaciHeap方法依次将min结点的所有孩子结点插入到根链表中，然后从根链表中删除掉min结点，并使堆结点数减一。此时如果根链表为空，则直接将min指针置为NULL，否则执行consolidate操作将根链表中所有度数相同的树合并。consolidate方法的执行过程如下图所示。

1. 数组A依次记录度数互不相同的树的根结点，例如，A[1]指向一颗度数为1的树的根结点。

3. 当循环过程中遇到A[n]等于本次迭代的结点时，说明合并已经结束，退出合并程序。

consolidate方法的代码如下所示。

```// 合并根链表中度数相同的结点
void consolidate(FibonaciHeap *heap)
{
int *A = (int *)malloc(sizeof(int)* heap->num);
for (int i = 0; i < heap->num; i++)	A[i] = NULL;

FibonaciNode *node = heap->min;
while (1)
{
if (A[node->num] != NULL)
{
FibonaciNode *n1 = node;
FibonaciNode *n2 = (FibonaciNode *)A[node->num];
if (n1 == n2)	break;	// 合并结束
if (n1->value > n2->value)
{
// 交换
exchangeFibonaciNode(n1, n2);
}
n2->left->right = n2->right;
n2->right->left = n2->left;
A[node->num] = NULL;
}
else
{
A[node->num] = (int)node;
node = node->right;
}
// 更新最小结点
if (node->value < heap->min->value)
{
heap->min = node;
}
}
free(A);
}```

4. 关键字减值

```// 关键字减值
void decreaseKey(FibonaciHeap *heap, FibonaciNode *node, int k)
{
if (k >= node->value)	return;

node->value = k;
FibonaciNode *parent = node->parent;
if (parent != NULL && node->value < parent->value)
{
cut(heap, node, parent);
cascandingCut(heap, parent);
}
if (node->value < heap->min->value)
{
heap->min = node;
}
}```

```// 从y中切除x并将x放置到根链表中
void cut(FibonaciHeap *heap, FibonaciNode *x, FibonaciNode *y)
{
x->left->right = x->right;
x->right->left = x->left;
if (y->child == x)	y->child = x->right;
if (y->child == x)	y->child = NULL;

insertIntoFibonaciHeap(heap, x);
x->parent = NULL;
x->mark = NONE;
}

// 递归切断mark为TRUE的结点
void cascandingCut(FibonaciHeap *heap, FibonaciNode *y)
{
FibonaciNode *p = y->parent;
if (p != NULL)
{
if (y->mark == FALSE)
{
y->mark = TRUE;
}
else if (y->mark == TRUE)
{
cut(heap, y, p);
cascandingCut(heap, p);
}
}
}```
cascandingCut方法向上回溯结点node的祖先结点，当发现有被删除两个孩子即mark为TRUE的结点时就调用cut方法将其切除并移植到根链表中，否则回溯结束。

5. 删除一个结点

```// 删除指定结点
bool deleteFromFibonaciHeap(FibonaciHeap *heap, FibonaciNode *node)
{
decreaseKey(heap, node, FIBONACI_MINUS_INF);
return extractMin(heap) == FIBONACI_MINUS_INF;
}```

<