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.improve

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