Fibonacci Heap

fibonacciheap.hpp

#include <vector>
#include <cmath>
#include <iostream>
#include <string>

#define D(n) log2(n)

class FibonacciException
{
	using string = std::string;
	string description;
public:
	FibonacciException(const string &str): description(str) {}
	string what() { return description; }
};

template <typename Key>
class FibonacciHeap
{
	template <typename T> using vector = std::vector<T>;
	
	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) {}
	};

	Node *_min = nullptr;
	int size = 0;

	void print(Node *li, int level)
	{
		if (li == nullptr)
			return;
		Node *ptr = li;
		do {
			for (int i = 0; i < level; i++)
				std::cout << ' ';
			std::cout << ptr->_key << "(" << ptr->_degree << ")" << std::endl;
			print(ptr->_children, level+1);
			ptr = ptr->_right;
		} while (ptr != li);
	} 

	// 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;
		}
	}

	// 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;
		}
	}

	// 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 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;
			}
	}

	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);
			}
		}
	}

	void destruct(Node *node)
	{
		if (node == nullptr)
			return;
		Node *ptr = node;
		do {
			Node *tmpNode = ptr;
			ptr = ptr->_right;
			if (tmpNode->_children)
				destruct(tmpNode->_children);
			delete tmpNode;
		} while (ptr != node);
	}

	// 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;
	}
public:
	FibonacciHeap() = default;

	FibonacciHeap(const FibonacciHeap &heap): size(heap.size), _min(copy(heap._min)) {}

	~FibonacciHeap()
	{
		destruct(_min);
	}

	// iterator: hide pointer
	class iterator
	{
		friend class FibonacciHeap;
		Node *_node;
		iterator(Node *node): _node(node) {}
	public:
		iterator(): _node(nullptr) {}
		Key operator *() { return _node->_key; }
	};

	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);
	}

	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;
	}

	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;
	}

	void decrease(iterator it, const Key &key)
	{
		decrease(it._node, key);
	}

	void print()
	{
		print(_min, 0);
	}
};