FibonacciHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <stdexcept>
#include <cmath> // maxDegree
 
namespace alib {
 
// fibonacci heap used as mergeable priority queue
template < typename T, typename Comparator = std::less < T > >
class FibonacciHeap {
public:
    FibonacciHeap ( Comparator comparator = Comparator ( ) ) : m_max( nullptr ), m_size( 0 ), m_comparator( comparator ) {
    }
 
    ~FibonacciHeap ( );
 
    // inserts a node with new value into the heap
    void insert ( const T & value );
 
    // finds the maximum value in the heap
    const T & getMax ( ) const {
        return m_max->value;
    }
 
    // finds and removes the maximum value from the heap
    T extractMax ( );
 
    // merges this heap with another heap (!! this is a DESTRUCTIVE merge, heap in argument will be cleared !!)
    void mergeWith ( FibonacciHeap< T, Comparator > && that );
 
    size_t size ( ) const {
        return m_size;
    }
 
//  void print ( );
 
//  void checkConsystency ( );
 
protected:
    struct Node {
        T value;
        unsigned degree;
        bool mark;
        Node * parent;
        Node * child;
        Node * prev;
        Node * next;
        Node(const T & val, unsigned deg = 0, Node * par = nullptr, Node * chld = nullptr, Node * pr = nullptr, Node * ne = nullptr)
         : value(val), degree(deg), mark(false), parent(par), child(chld), prev(pr), next(ne) {}
    };
 
    Node * m_max; //< pointer to cyclic doubly linked list of trees
    size_t m_size; //< count of elements stored in the heap
    Comparator m_comparator; //< user-defined comparator function
 
protected:
 
    // deletes one linked list of trees
    void deleteTreeList( Node * head );
 
    // connects doubly linked lists from 2 fibonacci heaps and returns address of head of the new linked list
    void mergeHeaps( Node * & max1, Node * & max2 );
 
    // goes through list of trees and merges trees with same degree
    void consolidate();
 
    // links tree to child list of node
    void linkTreeToNode( Node * node, Node * tree );
 
//  void printNode ( Node * node );
 
//  void checkConsystency ( Node * node, Node * parent );
};
 
 
template < typename T, typename Comparator >
FibonacciHeap< T, Comparator >::~FibonacciHeap ( ) {
    deleteTreeList( m_max );
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::deleteTreeList( Node * head ) {
    if ( ! head )
        return;
 
    Node * actual = head;
    do {
        Node * next = actual->next;
        deleteTreeList( actual->child );
        delete actual;
        actual = next;
    } while (actual != head);
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::insert( const T & value ) {
    Node * newNode = new Node( value, 0, nullptr, nullptr, nullptr, nullptr );
    newNode->prev = newNode;
    newNode->next = newNode; // make this node be a single-element cyclic list
 
    if (!m_max) {
        m_max = newNode; // this heap is empty, newNode becomes head of a linked list
        m_size = 1;
        return;
    }
 
    mergeHeaps( m_max, newNode ); // link the newNode into the existing linked list
 
    m_max = m_comparator ( newNode->value, m_max->value ) ? m_max : newNode;
 
    m_size++;
}
 
template < typename T, typename Comparator >
T FibonacciHeap< T, Comparator >::extractMax() {
    if ( m_max == nullptr )
        throw std::out_of_range ( "Heap is empty." );
 
    Node * z = m_max;
    T maxVal = z->value;
 
    if (z->child != nullptr) {
        Node * z1 = z->child;
        do {
            z1->parent = nullptr;
            z1 = z1->next;
        } while (z1 != z->child);
    }
 
    mergeHeaps ( z, z->child );
 
    if (z == z->next)
        m_max = nullptr;
    else {
        m_max = z->next;
        m_max->prev = z->prev;
        z->prev->next = m_max;
        consolidate();
    }
 
    m_size--;
    delete z;
    return maxVal;
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::mergeWith( FibonacciHeap< T, Comparator > && that ) {
    if (this->m_comparator != that.m_comparator) // nodes of these heaps are sorted by different condition
        throw std::logic_error("compare functions aren't equal, unable to merge");
 
    mergeHeaps( this->m_max, that.m_max ); // link the other heap into this heap
    this->m_max = m_comparator ( that.m_max->value, m_max->value ) ? this->m_max : that.m_max;
    that.m_max = nullptr;
 
    this->m_size += that.m_size;
    that.m_size = 0;
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::mergeHeaps( Node * & max1, Node * & max2 ) {
    if ( ! max1 ) {
        max1 = max2; // this heap is empty, move the content from the other heap inside
    } else if ( max2 ) {
        Node * max2prev = max2->prev;
 
        max2->prev->next = max1;
        max2->prev = max1->prev; // this magicaly works even if the lists contain only one node
        max1->prev->next = max2;
        max1->prev = max2prev;
    }
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::consolidate() {
    unsigned maxDegree = log2( m_size );
    Node * * rootsByDegree = new Node * [ maxDegree + 1 ];
    for (unsigned i = 0; i <= maxDegree; i++)
        rootsByDegree[i] = nullptr;
 
    Node * next = m_max;
    Node * actual = next;
 
    bool finish = next == next->next;
    while ( ! finish ) {
        actual = next;
        next = actual->next;
        finish = next == rootsByDegree [ next->degree ];
 
        while ( rootsByDegree[ actual->degree ] != nullptr) {
            Node * other = rootsByDegree[ actual->degree ];
            rootsByDegree[ actual->degree ] = nullptr;
 
            if ( m_comparator ( other->value, actual->value ) ) {
                linkTreeToNode( actual, other );
            } else {
                linkTreeToNode( other, actual );
                actual = other;
            }
 
        }
        rootsByDegree[ actual->degree ] = actual;
    };
 
    delete [] rootsByDegree;
 
    m_max = actual;
    Node * node = actual;
    do {
        if ( m_comparator ( m_max->value, node->value ) )
            m_max = node;
        node = node->next;
    } while ( node != actual );
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::linkTreeToNode( Node * node, Node * tree ) {
    tree->prev->next = tree->next;
    tree->next->prev = tree->prev;
 
    tree->prev = tree;
    tree->next = tree;
 
    tree->parent = node;
    node->degree ++;
 
    mergeHeaps ( node->child, tree );
}
 
/*template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::print() {
    if ( m_max == nullptr )
        std::cout << "Empty" << std::endl;
 
    printNode ( m_max );
}
 
template < typename T, typename Comparator >
void FibonacciHeap < T >::printNode ( Node * node ) {
    if ( node == nullptr )
        return;
 
    Node * actual = node;
    do {
        std::cout << " Value: " << actual->value << " Parent: " << ((actual->parent) ? actual->parent->id : -1) << " Left: " << actual->prev->id << " Right: " << actual->next->id << std::endl;
        printNode ( actual->child );
        actual = actual->next;
 
    } while ( node != actual );
}
 
template < typename T, typename Comparator >
void FibonacciHeap< T, Comparator >::checkConsystency() {
    checkConsystency ( m_max, nullptr );
}
 
template < typename T, typename Comparator >
void FibonacciHeap < T >::checkConsystency ( Node * node, Node * parent ) {
    if ( node == nullptr )
        return;
 
    Node * actual = node;
    do {
        assert ( node == node->prev->next && node->next->prev == node && node->parent == parent );
        checkConsystency ( actual->child, actual );
        actual = actual->next;
 
    } while ( node != actual );
}*/
 
} /* namespace alib */