斐波那契堆(二)之 C++的实现(二)
波那契堆是由一组最小堆组成，这些最小堆的根节点组成了双向链表(后文称为"根链表")；斐波那契堆中的最小节点就是"根链表中的最小节点"！
PS. 上面这幅图的结构和测试代码中的"基本信息"测试函数的结果是一致的；你可以通过测试程序来亲自验证！
2. 插入操作
插入操作非常简单：插入一个节点到堆中，直接将该节点插入到"根链表的min节点"之前即可；若被插入节点比"min节点"小，则更新"min节点"为被插入节点。
上面是插入操作的示意图。
斐波那契堆的根链表是"双向链表"，这里将min节点看作双向联表的表头(后文也是如此)。在插入节点时，每次都是"将节点插入到min节点之前(即插入到双链表末尾)"。此外，对于根链表中最小堆都只有一个节点的情况，插入操作就很演化成双向链表的插入操作。
此外，插入操作示意图与测试程序中的"插入操作"相对应，感兴趣的可以亲自验证。
插入操作代码
复制代码
/*
* 将node堆结点加入root结点之前(循环链表中)
* a …… root
* a …… node …… root
*/
template
void FibHeap::addNode(FibNode *node, FibNode *root)
{
node->left = root->left;
root->left->right = node;
node->right = root;
root->left = node;
}
/*
* 将节点node插入到斐波那契堆中
*/
template
void FibHeap::insert(FibNode *node)
{
if (keyNum == 0)
min = node;
else
{
addNode(node, min);
if (node->key < min->key)
min = node;
}
keyNum++;
}
复制代码
3. 合并操作
合并操作和插入操作的原理非常类似：将一个堆的根链表插入到另一个堆的根链表上即可。简单来说，就是将两个双链表拼接成一个双向链表。
上面是合并操作的示意图。该操作示意图与测试程序中的"合并操作"相对应！
合并操作代码
复制代码
/*
* 将双向链表b链接到双向链表a的后面
*
* 注意： 此处a和b都是双向链表
*/
template
void FibHeap::catList(FibNode *a, FibNode *b)
{
FibNode *tmp;
tmp = a->right;
a->right = b->right;
b->right->left = a;
b->right = tmp;
tmp->left = b;
}
/*
* 将other合并到当前堆中
*/
template
void FibHeap::combine(FibHeap *other)
{
if (other==NULL)
return ;
if(other->maxDegree > this->maxDegree)
swap(*this, *other);
if((this->min) == NULL) // this无"最小节点"
{
this->min = other->min;
this->keyNum = other->keyNum;
free(other->cons);
delete other;
}
else if((other->min) == NULL) // this有"最小节点" && other无"最小节点"
{
free(other->cons);
delete other;
} // this有"最小节点" && other有"最小节点"
else
{
// 将"other中根链表"添加到"this"中
catList(this->min, other->min);
if (this->min->key > other->min->key)
this->min = other->min;
this->keyNum += other->keyNum;
free(other->cons);
delete other;
}
}