斐波那契堆
2014-05-08 21:14:18 最后更新: 2014-06-18 00:03:23 访问数量：1735
概述
二项堆可以以 O(lgn) 的最坏时间复杂度完成 INSERT、MINIMUM、EXTRACT-MIN 和 UNION、DECREASE-KEY、DELETE 等堆操作，斐波那契堆具有和二项堆类似的功能和结构，但是只要不涉及删除元素的操作，他只需要 O(1) 的平摊时间复杂度
但是斐波那契堆的常数因子以及程序设计上的复杂性使他对大多数应用来说并不如通常的二叉堆或 K 叉堆合适
斐波那契堆的构成
和二项堆一样，斐波那契堆也是由一组树构成的，事实上，斐波那契堆是松散地基于二项堆的，松散的结构可以改善渐进时间界，对这种结构的维护工作可以被延迟到方便的时候再做
斐波那契堆的树结构如下图所示：
与二项堆一样，斐波那契堆是由一组树构成的，但不同的是，斐波那契堆中的树是有根但无序的，每个节点包含一个指向其父节点的指针、一个指向其任一子女的指针、左右兄弟指针，每个节点的子女都被链接成一个环形双向链表，成为该节点的子女表同时，每一个节点有一个标记度数的域 degree，用来记录子女个数
采用环形双向链表有两个好处，首先可以在 O(1) 时间内将节点从链表中去掉，同时，给定两个这样的表，可以在 O(1) 时间内将他们连在一起，组成新的环形双向链表
堆的根所在的双向链表被称为根表，min 指针指向堆的根表中的最小元素，即堆的根
可合并堆操作
与二项堆一样，斐波那契堆也支持最基本的 MAKE-HEAP、INSERT、MINIMUM、EXTRACT-MIN 和 UNION 操作，但是斐波那契堆只在 EXTRACT-MIN 操作中进行堆的结构调整，同时斐波那契堆的结构又十分松散，因此，其他操作的实现就非常容易了
1、插入节点
由于斐波那契堆的结构与二项堆非常相似，所以插入过程也和二项堆一样，新的元素作为一个新的二项树的根节点被插入根表中，但与二项堆不同的是，斐波那契堆并不对堆中的树进行合并操作，以获取更高的平摊代价
2、合并两个斐波那契堆
斐波那契堆的合并只需要将两个根表连接并选出新的最小根即可，可以在 O(1) 时间内完成
3、抽取最小节点
斐波那契堆的关键思想是尽可能的将工作推后，在插入节点和合并堆的过程中都没有进行的合并树操作都被推迟到了抽取最小节点的操作中了，因此，抽取最小节点也就成为了斐波那契堆实现中最复杂的操作了
斐波那契堆的实现
/*
* file: function.h
* date: 2014-04-28
* author: 龙泉居士
*/
#ifndef FUNCTION_H_20131216
#define FUNCTION_H_20131216
class Fibo_heap
{
private:
struct Node
{
Node(int key);
int key;
int degree;
Node *left;
Node *right;
Node *parent;
Node *son;
};
void union_same_degree();
Node *link_tree(Node *node1, Node *node2); // node1->key < node2->key
void link_list(Node *node1, Node *node2); // node1 和 node2 不能在同一个环上
void update_min();
public:
Fibo_heap();
Node *min;
int tree_num;
void insert(int elem);
void union_heap(Fibo_heap *heap);
int minimum();
Node *extract_min();
void remove(Node *node);
void print();
};
#endif
/*
* file: function.cc
* date: 2014-04-28
* author: 龙泉居士
*/
#include <iostream>
#include <stack>
#include <map>
#include "function.h"
using namespace std;
Fibo_heap::Node::Node (int key)
{
this->key = key;
degree = 0;
left = right = this;
parent = son = NULL;
}
Fibo_heap::Fibo_heap ():min(NULL),tree_num(0) { }
void Fibo_heap::insert (int elem)
{
if (min == NULL)
{
min = new Node(elem);
}
else
{
Node *temp_node = new Node(elem);
temp_node->right = min->right;
temp_node->left = min;
min->right->left = temp_node;
min->right = temp_node;
if (elem < min->key)
min = temp_node;
}
++tree_num;
}
void Fibo_heap::link_list(Fibo_heap::Node *node1, Fibo_heap::Node *node2)
{
if (node1 == NULL || node2 == NULL)
return;
node1->right->left = node2->left;
node2->left->right = node1->right;
node1->right = node2;
node2->left = node1;
}
void Fibo_heap::union_heap (Fibo_heap *heap)
{
if (min == heap->min)
return;
link_list(min, heap->min);
if (min == NULL || min->key > heap->min->key)
min = heap->min;
tree_num += heap->tree_num;
}
int Fibo_heap::minimum ()
{
if (min != NULL)
return min->key;
return -1;
}
Fibo_heap::Node *Fibo_heap::extract_min ()
{
if (min == NULL)
return min;
if (min->son != NULL)
{
link_list(min->son, min);
min->son->parent = NULL;
min->son = NULL;
}
else
--tree_num;
Node *temp_node = min;
if (min->right == min)
{
min = NULL;
return temp_node;
}
min->right->left = min->left;
min->left->right = min->right;
min = min->right;
union_same_degree();
return temp_node;
}
void Fibo_heap::union_same_degree()
{
map<int, Node*> degree_map;
Node *temp_node = min;
if (min == NULL)
return;
while (1)
{
if (degree_map.find(temp_node->degree) != degree_map.end() && degree_map[temp_node->degree] != temp_node)
{
if (degree_map[temp_node->degree]->key > temp_node->key)
{
link_tree(degree_map[temp_node->degree], temp_node);
degree_map.erase(temp_node->degree-1);
}
else
{
link_tree(temp_node, degree_map[temp_node->degree]);
temp_node = degree_map[temp_node->degree];
degree_map.erase(temp_node->degree);
}
--tree_num;
}
else
{
degree_map[temp_node->degree] = temp_node;
temp_node = temp_node->right;
}
if (degree_map.size() > (size_t)tree_num)
break;
}
if (temp_node != NULL)
{
min = temp_node;
update_min();
}
}
Fibo_heap::Node *Fibo_heap::link_tree(Fibo_heap::Node *node1, Fibo_heap::Node *node2)
{
if (node1 == node2 || node1 == NULL || node2 == NULL)
return NULL;
node1->left->right = node1->right;
node1->right->left = node1->left;
node1->left = node1;
node1->right = node1;
if (node2->son == NULL)
node2->son = node1;
else
link_list(node1, node2->son);
node1->parent = node2;
node2->degree++;
if (min == node1)
min = node2;
return node2;
}
void Fibo_heap::remove (Fibo_heap::Node *node)
{
if (node == NULL)
return;
if (node->son != NULL)
{
node->son->parent = node->parent;
link_list(node, node->son);
if (node->parent != NULL && node->parent->son == node)
node->parent->son = node->son;
if (min == node)
{
min = node->son;
update_min();
}
}
node->left->right = node->right;
node->right->left = node->left;
delete node;
}
void Fibo_heap::update_min ()
{
if (min == NULL)
return;
Node *temp_node = min;
Node *node = temp_node;
while (1)
{
if (min->key > temp_node->key)
min = temp_node;
temp_node = temp_node->right;
if (temp_node == node)
break;
}
}
void Fibo_heap::print ()
{
Node *temp_node = min;
if (min == NULL)
return;
while (1)
{
cout << temp_node->key << ' ';
if (temp_node->son == NULL)
{
temp_node = temp_node->right;
while (1)
{
if (temp_node == min)
{
cout << endl;
return;
}
if (temp_node->parent == NULL || temp_node != temp_node->parent->son)
break;
cout << "\nparent" << endl;
temp_node = temp_node->parent->right;
}
}
else
{
cout << "\nson" << endl;
temp_node = temp_node->son;
}
}
}