Federico Mengozzi

A new slightly improved version

Improving the Fibonacci Heap

Add a nodes pool and make it mergeable

Since my old post on the fibonacci-heap I made a few changes in the structure, cleaned the code and I had the chances to perform some other tests.

The real improvement over the last version was creating a nodes pool instead of allocate a new node on every call to insert. The idea is to create a stack of pre-allocated node object (by default a stack of $1000$ nodes) and use them as they are needed. In addition, instead of deleting a node when it’s extracted, it’s sufficient to clear it and put it back in the stack.

To do this other utility methods are used

class fibonacci_heap_node {
    //...

    fibonacci_node() : p(nullptr), left(this), right(this), child_list(), degree(0), mark(false) {}
    // If obj are modified after being insrted something bad could happen
    fibonacci_node(KEY_NODE &k, DATA_NODE &d) :  fibonacci_node<KEY_NODE, DATA_NODE>() {
        key = k;
        data = d;
    }

    void clear() {
        p = nullptr;
        left = this;
        right = this;
        child_list = doubly_linked_list<fibonacci_node<KEY_NODE, DATA_NODE> *>();
        degree = 0;
        mark = false;
    }

    //...
}
class fibonacci_heap {
    //...

    void fill_pool(){
        for(int i=0; i<POOL_SIZE; i++){
            pool.push(new fibonacci_node<KEY, DATA>());
        }
    }

    fibonacci_node<KEY, DATA> *get_node(KEY &k, DATA &d){
        fibonacci_node<KEY, DATA> *x = pool.top();
        pool.pop();
        x->key = k;
        x->data = d;
        if(pool.size() == 0)
            fill_pool();
        return x;
    }

    //...
}

Another change in the structure was the possibility to add an ordering function for the structure. In this way was possible to have both a min-fibonacci heap and max-fibonacci heap with same implementation. Instead of directly compare the key of the node, now the compare function is used

class fibonacci_heap {
    //...
    
    // the constructor now support passing a function
    fibonacci_heap(std::function<bool(KEY, KEY)> cmp) : nodes(0), top_node(nullptr), addresses(), compare(cmp) {
        fill_pool();
    }
    
    // by default it's a min heap
    fibonacci_heap(int size, KEY default_key, std::function<bool(KEY, KEY)> cmp = [](KEY k1, KEY k2){ return k1 < k2;}) : fibonacci_heap<KEY, DATA>(cmp) { 
        fill(size, default_key);
    }

    //...
}

int main(){
    // how the heap is created now
    fibonacci_heap<int, std::string> F1([](int k1, int k2){ return k1 < k2;});
}

Finally the merge method was implemented (really simple, it consists in merging the two root_list) and I also performed some refactor. The final version is below.

#include <vector>
#include <cmath>
#include <iostream>
#include <unordered_map>
#include <iostream>
#include <functional>
#include <stack>

/**
 *  usage example in SP's algorithm
 *  the KEY would be the distance to each node, initialized at INF
 *  the DATA would be an identifier for the node itself
 *  for this reason all element's DATA should be different from one another while
 *  it's reasonable to have two element with the same KEY
 *
 *  C++11 or above
 *
 **/

// fibonacci heap
template <typename KEY, typename DATA>
class fibonacci_heap {
private:
	// doubly linked list template
	template <typename T>
	class doubly_linked_list {
	private:
		T _head;
		size_t _size;
	
		void insert_after(T prev, T node) {
			if (prev != nullptr) {
				node->left = prev;
				node->right = prev->right;
				prev->right->left = node;
				prev->right = node;
			}
			++_size;
		}

	public:

		doubly_linked_list() : _head(nullptr), _size(0) {};

		T head() { return _head; }

		void remove(T node) {          // remove node from list and clear its pointers
			if (_size == 1) {
				_head = nullptr;
			} else if (node == _head) {
				_head = node->right;
			}
			node->right->left = node->left;
			node->left->right = node->right;
			node->left = node;
			node->right = node;
			--_size;
		}
		
		void push_back(T node) {            // append the node at the tail of the list
			if (empty()) insert_after(_head = node, node);
			else insert_after(_head->left, node);
		}

		void merge(doubly_linked_list &l) {
			T last_node = _head->left;
			_head->left = l._head->left;
			l._head->left->right = _head;
			l._head->left = last_node;
			last_node->right = l._head;
			_size += l.size();
		}

		void print() {
			T n = _head;
			do {
				std::cout << n->key << " @" << n << std::endl;
				n = n->right;
			} while (n != _head);
		}
		
		bool empty() { return !_size; }
		
		ssize_t size() { return _size; }
		
		void clear() { _head = nullptr, _size = 0; }
	};

	template <typename KEY_NODE, typename DATA_NODE>
	class fibonacci_heap_node {
	public:

		fibonacci_heap_node<KEY_NODE, DATA_NODE> *p, *left, *right;
		doubly_linked_list<fibonacci_heap_node<KEY_NODE, DATA_NODE> *> child_list;
		ssize_t degree;
		bool mark;
		KEY_NODE key;
		DATA_NODE data;

		fibonacci_heap_node() : p(nullptr), left(this), right(this), child_list(), degree(0), mark(false) {}
		// If obj are modified after being inseted something bad could happen
		fibonacci_heap_node(KEY_NODE &k, DATA_NODE &d) :  fibonacci_heap_node<KEY_NODE, DATA_NODE>() {
			key = k;
			data = d;
		}

		void clear() {
			p = nullptr;
			left = this;
			right = this;
			child_list = doubly_linked_list<fibonacci_heap_node<KEY_NODE, DATA_NODE> *>();
			degree = 0;
			mark = false;
		}
		 
		bool operator< (const fibonacci_heap_node x){ return key < x.key; }
		bool operator> (const fibonacci_heap_node x){ return key > x.key; }
	};

	const int POOL_SIZE = 1000;
	ssize_t nodes;
	// pool implemented using a stack instead of a queue 
	// to reuse nodes as soon as possible (cache friendly?)
	std::stack<fibonacci_heap_node<KEY, DATA> *> pool;
	fibonacci_heap_node<KEY, DATA> *top_node;
	doubly_linked_list<fibonacci_heap_node<KEY, DATA> *> root_list;
	std::unordered_map<DATA, fibonacci_heap_node<KEY, DATA> *> addresses;
	std::function<bool(KEY, KEY)> compare;

	void consolidate() {
		std::vector<fibonacci_heap_node<KEY, DATA> *> pointers(max_degree(), nullptr);
		fibonacci_heap_node<KEY, DATA> *node = top_node, *x, *y;

		for(ssize_t i=0; i<root_list.size(); ++i){
			node = (x = node)->right;   // x = node, node = x->right
			ssize_t d = x->degree;
			while (pointers[d]) {
				y = pointers[d];
				if (!compare(x->key, y->key))
					std::swap(x, y);
				make_child(y, x);
				pointers[d] = nullptr;
				++d, --i;
			}
			pointers[d] = x;
		}
		root_list.clear();
		top_node = nullptr;
		for (auto &x: pointers) {
			if (x) {
				root_list.push_back(x);
				if (top_node == nullptr) {
					top_node = x;
				} else if (compare(x->key, top_node->key)) {
					top_node = x;
				}
			}
		}
	}
	
	void cut(fibonacci_heap_node<KEY, DATA> *x, fibonacci_heap_node<KEY, DATA> *y) {
		y->child_list.remove(x);
		--y->degree;
		root_list.push_back(x);
		x->p = nullptr;
		x->mark = false;
	}
	
	void cascading_cut(fibonacci_heap_node<KEY, DATA> *y) {
		fibonacci_heap_node<KEY, DATA> *z = y->p;
		while(z != nullptr){
			if(y->mark == false){
				y->mark = true;
				z = nullptr;
			} else {
				cut(y, z);
				z = (y = z)->p;
			}
		}
	}
	
	void make_child(fibonacci_heap_node<KEY, DATA> *y, fibonacci_heap_node<KEY, DATA> *x) {
		root_list.remove(y);
		x->child_list.push_back(y);
		++x->degree;
		y->p = x;
		y->mark = false;
	}
	
	void insert(fibonacci_heap_node<KEY, DATA> *node) {
		addresses[node->data] = node;
		root_list.push_back(node);
		if (top_node == nullptr) {
			top_node = node;
		} else if(compare(node->key, top_node->key)) {
			top_node = node;
		}
		++nodes;
	}
	
	// upper_bound of number of root nodes in the root lists that will be present after consolidation
	ssize_t max_degree() { return (ssize_t)floor(log((double)nodes)/log((1.0+sqrt(5.0))/2.0))+1; }

	void fill_pool(){
		for(ssize_t i=0; i<POOL_SIZE; i++){
			pool.push(new fibonacci_heap_node<KEY, DATA>());
		}
	}

	fibonacci_heap_node<KEY, DATA> *get_node(KEY &k, DATA &d){
		fibonacci_heap_node<KEY, DATA> *x = pool.top();
		pool.pop();
		x->key = k;
		x->data = d;
		if(pool.size() == 0)
			fill_pool();
		return x;
	}

public:
	fibonacci_heap(std::function<bool(KEY, KEY)> cmp) : nodes(0), top_node(nullptr), addresses(), compare(cmp) {
		fill_pool();
	}
	
	void insert(KEY k, DATA d) { insert(get_node(k, d)); }

	std::pair<KEY, DATA> get() {
		return {top_node->key, top_node->data};
	}
	
	void remove(){
		fibonacci_heap_node<KEY, DATA> *extracted = top_node;
		if (extracted != nullptr) {
			while (extracted->child_list.size()) {
				fibonacci_heap_node<KEY, DATA> *child = extracted->child_list.head()->right;
				extracted->child_list.remove(child);
				child->p = nullptr;
				root_list.push_back(child);
			}
			fibonacci_heap_node<KEY, DATA> *next_node = extracted->right;
			root_list.remove(extracted);
			if (extracted == next_node) {
				top_node = nullptr;
			} else {
				top_node = next_node;
				consolidate();
			}
			--nodes;
			addresses.erase(extracted->data);
			extracted->clear();
			pool.push(extracted);
		}
	}
	
	void update_key(KEY key, DATA data) {
		if(addresses.count(data) == 0) return;
		fibonacci_heap_node<KEY, DATA> *node = addresses[data];
		if (compare(key, node->key)) {
			node->key = key;
			fibonacci_heap_node<KEY, DATA> *parent = node->p;
			if (parent != nullptr && compare(node->key, parent->key)) {
				cut(node, parent);
				cascading_cut(parent);
			}
			if (compare(node->key, top_node->key)) {
				top_node = node;
			}
		}
	}

	void merge(fibonacci_heap<KEY, DATA> &other) {
		root_list.merge(other.root_list);

		if(top_node == nullptr || (other.top_node != nullptr && compare(other.top_node->key, top_node->key)))
			top_node = other.top_node;
		
		nodes += other.size();
	}
 
	ssize_t size() { return nodes; }
};
Go to top