斐波那契堆是一种理论上优于二向堆的数据结构,对比二向堆,斐波那契堆的优势在插入、合并、减值。不同于常见的二叉树、二向堆那样可以直观地计算出各种操作需要的时间复杂度,斐波那契堆的复杂度计算需要一些技巧。完整的斐波那契堆实现见Gist

操作 二向堆(最坏) 斐波那契堆(摊还)
创建 O(1) O(1)
插入 O(lgn) O(1)
访问最小值 O(1) O(1)
弹出最小值 O(lgn) O(lgn)
合并 O(n) O(1)
减值 O(lgn) O(1)
删除某个元素 O(lgn) O(lgn)

图(a)就是斐波那契堆的结构了,一个链表将多个堆连接到了一起,每个堆中的元素需要满足(最小)堆的性质:子元素大于父元素。除此之外,还有一个min指针,指向整个数据结构中最小的节点。斐波那契堆之所以能够更加高效,基于以下事实:

对于一个有着n个元素斐波那契堆,任何一个节点的子节点个数(度数)不超过D(n)=O(lgn)。

节点定义

图(b)体现了数据结构中真实的指针连接情况,由此可以定义节点的结构体:

struct Node
{
	Key _key;
	bool _mark;
	int _degree;
	Node *_left, *_right, *_children, *_parent;
	Node(const Key &key): _mark(false), _key(key), _degree(0),
		_left(nullptr), _right(nullptr), _children(nullptr), _parent(nullptr) {}
};
  • key:关键字,需要有可比性;

  • mark:是否在成为其他节点的子节点后,失去过子节点,这个属性用来确保一个不处于根节点上的节点不会失去一个以上的子节点,是算法分析时需要用到的一个重要性质;

  • degree:子节点的数量;

  • left, right, children, parent:指向左兄、右兄、孩子节点、父节点的指针。

迭代器

斐波那契堆有修改某个数值的操作,Node类是斐波那契堆的私有类,直接暴露Node对象指针是不对的,需要对器进行封装:

// iterator: hide pointer
class iterator
{
	friend class FibonacciHeap;
	Node *_node;
	iterator(Node *node): _node(node) {}
public:
	iterator(): _node(nullptr) {}
	Key operator *() { return _node->_key; }
};
提示:显然,这个迭代器的设计不太好。当迭代器指向的元素从数据结构中删除后,访问迭代器元素将发生错误。

插入

直接将元素插入根链表,如果新插入的元素小于插入前的最小元素,那么需要更新斐波那契堆中的最小元素,最后返回插入元素的迭代器。这个操作显然是常数时间复杂度。

经常需要用到链表插入操作,定义一个函数来处理会方便很多。

// insert node in a bidirection linked list
void insert(Node *&head, Node *node)
{
	if (head == nullptr) {	// empty: create a list
		node->_left = node;
		node->_right = node;
		head = node;
	} else {				// not empty: append to tail
		Node *prev = head->_left;
		node->_left = prev;
		node->_right = head;
		prev->_right = node;
		head->_left = node;
	}
}

iterator insert(const Key &key)
{
	Node *node = new Node(key);
	insert(_min, node);
	// update minimum item
	if (key < _min->_key)
		_min = node;
	size++;
	return iterator(node);
}

合并

合并操作只需要将两个链表合并,然后选取两个链表中最小的元素作为最小元素,复杂度为常数。不过,如果不想破坏原有的数据结构,那就需要进行复杂度为O(n)的拷贝。。。

// copy fibonacci heap
Node *copy(Node *node, Node *parent = nullptr)
{
	// empty list
	if (node == nullptr)
		return nullptr;
	Node *head = nullptr;
	Node *ptr = node;
	do {
		Node *newNode = new Node(*ptr);
		newNode->_parent = parent;
		newNode->_children = nullptr;
		// copy children
		if (ptr->_children)
			newNode->_children = copy(ptr->_children, newNode);
		insert(head, newNode);
		ptr = ptr->_right;
	} while (ptr != node);
	return head;
}

FibonacciHeap uni(const FibonacciHeap &heap)
{
	// empty heap
	if (_min == nullptr)
		return heap;
	else if (heap._min == nullptr)
		return (*this);
	// combine two root list
	FibonacciHeap<Key> newHeap;
	Node *li1 = copy(_min);
	Node *li2 = copy(heap._min);
	Node *prev1 = li1->_left;
	Node *prev2 = li2->_left;
	li1->_left = prev2;
	li2->_left = prev1;
	prev2->_right = li1;
	prev1->_right = li2;
	// construct new heap
	newHeap._min = li1->_key < li2->_key ? li1 : li2;
	newHeap.size = size + heap.size;
	return newHeap;
}

获取最小元素

获取最小元素只需要常数时间。

Key min()
{
	Key minKey;
	if (_min)
		minKey = _min->_key;
	return minKey;
}

弹出最小元素

接下来需要用到删除操作。

// remove node from a bidirection linked list
void remove(Node *&head, Node *node)
{
	if (node->_left == node && node->_right == node) {	// node is the only one
		head = nullptr;
	} else {
		if (head == node)								// node is the head
			head = node->_right;
		node->_right->_left = node->_left;
		node->_left->_right = node->_right;
	}
}

要删除最小元素,首先要把最小元素的所有子节点移动到根节点中,然后将最小元素节点删除,最后需要对斐波那契堆进行整理。

Key extractMin()
{
	Key minKey;
	Node *minPtr = _min;
	if (minPtr) {
		minKey = minPtr->_key;
		// move children of min into the root list
		while (minPtr->_children) {
			Node *child = minPtr->_children;
			remove(minPtr->_children, child);
			insert(_min, child);
			_min->_parent = nullptr;
		}
		// remove min
		remove(_min, minPtr);
		if (_min)
			consolidate();
		size--;
		delete minPtr;
	}
	return minKey;
}

进行整理前,创建一个数组用来存储各种度数不同的节点,因为度数范围为[0,D(n)],所以数组大小为D(n)+1。每次从根链表中取出一个节点,如果节点数组中存在和该节点度数相同的节点,那么将关键字大的节点链接为关键字较大节点的子节点,父节点的度数加一。反复进行链接,直到不存在度数相同的节点,最后将新的节点加入数组。当根链表中的所有节点被处理完之后,需要重新构造一个根链表,将数组中的全部节点取出,链接为根链表。

void consolidate()
{
	vector<Node*> a(D(size)+1, nullptr);
	// link
	while (_min) {
		Node *ptr = _min;
		remove(_min, ptr);
		int d = ptr->_degree;
		while (a[d]) {
			Node *child = a[d];
			if (ptr->_key > child->_key)
				std::swap(ptr, child);
			link(child, ptr);
			a[d] = nullptr;
			d++;
		}
		a[d] = ptr;
	}
	// construct root list
	for (Node *ptr : a)
		if (ptr) {
			insert(_min, ptr);
			if (_min->_key > ptr->_key)
				_min = ptr;
		}
}

// add child into parent's children list
void link(Node *child, Node *parent)
{
	insert(parent->_children, child);
	parent->_degree++;
	child->_parent = parent;
	child->_mark = false;
}

减值

当一个节点的关键字减小后,需要将这个节点移到根节点中。这个时候需要确保父节点(非根结点)不会失去超过两个孩子。父节点就失去了一个孩子,如果是第一次失去孩子,那么打上标记即可。如果是第二次失去孩子,那么需要将这个父节点同样移到根链表中,接着,爷节点(如果有的话)也要同样的操作。当所有的标记过的租先节点被处理完之后,更新最小节点。

void decrease(Node *node, const Key &key)
{	
	if (key > node->_key)
		throw FibonacciException("new key is greater than old key");
	node->_key = key;
	Node *parent = node->_parent;
	if (parent && parent->_key > node->_key) {
		cut(node, parent);
		cascadingCut(parent);
	}
	// update minimum
	if (node->_key < _min->_key)
		_min = node;
}

// move child into root list
void cut(Node *child, Node *parent)
{
	remove(parent->_children, child);
	insert(_min, child);
	child->_parent = nullptr;
	child->_mark = false;
}

void cascadingCut(Node *node)
{
	Node *parent = node->_parent;
	if (parent) {
		if (parent->_mark == false) {	// lost a child for fisrt time
			parent->_mark = true;
		} else {						// lost a child for second time
			cut(node, parent);
			cascadingCut(parent);
		}
	}
}