鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

斐波那契堆

来源:互联网 作者:佚名 时间:2016-06-11 09:27
本文将要介绍的斐波那契堆是一种保有最小堆性质的“森林集合”。和二叉堆一样,他可以用来实现优先队列,而且比二叉堆在某些操作上有更优的时间复杂度。比如插入操作,二叉堆插入一个结点需要从底向上调整堆结构,因此需要O(lgn)的时间,而斐波那契堆则只需

本文将要介绍的斐波那契堆是一种保有最小堆性质的“森林集合”。和二叉堆一样,他可以用来实现优先队列,而且比二叉堆在某些操作上有更优的时间复杂度。比如插入操作,二叉堆插入一个结点需要从底向上调整堆结构,因此需要O(lgn)的时间,而斐波那契堆则只需要O(1)的时间。下面将会解析斐波那契堆的各个基本操作及其c/cpp实现代码。下面是一个斐波那契堆的结构示意图。除了插入操作,斐波那契堆总是保持着一个性质:每棵树的度数都不一样。

斐波那契堆持有一个双链表,该双链表维护的是一系列树的根结点,称为根链表,且该链表首尾相连。根链表中每一个根结点都可能指向一个双链表中的某一个结点,该链表为其孩子链表。以森林的结构角度来看,斐波那契堆的结构如上图a所示,以指针指向的具体关系角度来看,斐波那契堆的结构如上图b所示。斐波那契堆有一个min指针指向根链表中的最小结点。因为斐波那契堆中每一棵树都具有最小堆性质,因此min指针指向的根结点也是整个斐波那契堆中的最小结点。下面是一个斐波那契堆数据结构的定义。

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为斐波那契堆中一个结点的数据结构定义,其中value为结点的值,mark用来记录结点的一些历史信息,后面会用到,num为该结点的孩子结点数量。FibonaciHeap是斐波那契堆的数据结构定义,其维护一个指向min结点的指针以及记录整个堆的结点数量的num变量。

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

初始化时,mark为none;

当结点从一个根变为另一个根结点的孩子结点时,mark为FALSE;

当结点被删除一个孩子时,mark为TRUE。

当mark为TRUE时,若结点还要被删除一个孩子,则将结点从其父结点中切除,并移植到根链表中。

上述操作都是在删除一个结点的时候对斐波那契堆进行调整时需要使用到的。

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. 插入一个结点

斐波那契堆插入一个结点的操作非常简单,只需要在min结点的前/后直接插入即可,其相当于一个双链表的插入操作。向一个斐波那契堆中插入一个结点的操作如下图所示。

上图所示将值为21的新结点直接插入到min结点的前面。实现代码如下,记得要判断是否需要更新min结点,还要更新堆的结点数。

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. 提取最小结点

提取最小结点直接将min结点返回即可,关键是提取了min结点之后的处理。如果min结点么有孩子结点,那么提取min结点只是简单的双链表删除结点操作。但如果min结点有孩子结点,那就需要对删除min结点后的这些剩余的孩子结点进行处理,并保持斐波那契堆每棵树的度数都不一样的要求。

首先,将min结点的所有孩子结点插入到根链表中;

然后,将根链表中所有具有相同度数的树合并。

合并的具体方法是,将根的值较大的树连接到根的值较大的树的孩子链表中。

将两棵树合并的程序如下。

// 将结点c作为孩子结点插入到结点p的孩子链表中
void linkFibonaciTree(FibonaciNode *p, FibonaciNode *c)
{
	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;
}
这里因为结点c被移植到了结点p的孩子链表中,所以结点c的mark被置为FALSE。

提取最小结点的代码如下所示。

// 提取最小结点
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方法的执行过程如下图所示。

图a为提取最小结点前的斐波那契堆,图b为将min结点的孩子结点插入到根链表并删除min结点后的堆,此时min结点指向值为17的结点。图c到图m为consolidate的过程:

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

2. 从图b的min指针指向的结点开始,设该结点的度数为n,考察A[n]是否为NULL,否则将该结点与A[n]指向的结点合并(调用linkFibonaciTree方法),然后将A[n]置为NULL;若A[n]为NULL,则将A[n]指向该结点,然后判断是否需要更新min指针的指向,并跳到下一个结点重复上述操作。

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;
			linkFibonaciTree(n1, n2);
		}
		else
		{
			A[node->num] = (int)node;
			node = node->right;
		}
		// 更新最小结点
		if (node->value < heap->min->value)
		{
			heap->min = node;
		}
	}
	free(A);
}
根据《算法导论》的分析,提取最小结点的操作的时间复杂度为O(lgn)。

4. 关键字减值

对斐波那契堆中一个结点的值做变小操作后,可能会违反其最小堆性质(比起父结点小),因此就需要进行调整。调整主要是通过剪切操作实现的。

上图中图a~b是将值为46的结点变小为15时的调整操作;图c~e为将值为35的结点变为5时的调整操作。调整操作的代码如下所示。

// 关键字减值
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;
	}
}
首先将关键字值比父结点要小的结点node通过cut方法从其父结点中切除并移植到根链表中,然后再对node的父结点parent进行cascandingCut操作向上切除。cut方法和canscandingCut方法的代码如下所示。

// 从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方法将其切除并移植到根链表中,否则回溯结束。

其实说实话,我并不明白这个cascandingCut操作是干啥的,我只是隐约觉得如果不这样干,在连续删除几个结点后,斐波那契堆中的树会变了样。。。大家可以参考下面链接中的解释。

点击打开链接

5. 删除一个结点

这个操作以关键字减值的操作为基础,实现非常简单。只需要对要删除的结点的值变为无穷小,通过调整后该结点一定会被放到根链表中,然后就只需要执行extractMin操作即可。

// 删除指定结点
bool deleteFromFibonaciHeap(FibonaciHeap *heap, FibonaciNode *node)
{
	decreaseKey(heap, node, FIBONACI_MINUS_INF);
	return extractMin(heap) == FIBONACI_MINUS_INF;
}
删除操作的时间复杂度为O(lgn)。

6. 总结

完整的程序可以看到我的github项目 数据结构与算法

这个项目里面有本博客介绍过的和没有介绍的以及将要介绍的《算法导论》中部分主要的数据结构和算法的C实现,有兴趣的可以fork或者star一下哦~ 由于本人还在研究《算法导论》,所以这个项目还会持续更新哦~ 大家一起好好学习~
网友评论
<