BinomialHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <stdexcept>
 
namespace alib {
 
// binomial heap used as mergeable priority queue
template < typename T, typename Comparator = std::less < T > >
class BinomialHeap {
public:
 
    BinomialHeap ( Comparator comparator = Comparator ( ) ) : m_head( nullptr ), m_size( 0 ), m_comparator ( comparator ) {
    }
 
    ~BinomialHeap ( );
 
    // 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 ( * searchMax ( const_cast < Node * * > ( & m_head ) ) )->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 ( BinomialHeap< T, Comparator > && that );
 
    size_t size ( ) const {
        return m_size;
    }
 
protected:
 
    struct Node {
        T value;
        unsigned degree;
        Node * parent;
        Node * child;
        Node * sibling;
        Node( const T & val, unsigned deg = 0, Node * par = nullptr, Node * chld = nullptr, Node * sib = nullptr )
         : value ( val ), degree ( deg ), parent ( par ), child ( chld ), sibling ( sib ) { }
    };
 
    Node * m_head; //< head of a singly linked list of binomial 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 binomial trees
    void deleteTreeList( Node * head );
 
    // searches the linked list and returns address of variable pointing to the node with maximum value
    Node * * searchMax( Node * * head ) const;
    // merges linked lists from 2 binomial heaps and returns address of head of the new linked list
 
    Node * mergeHeaps( Node * head1, Node * head2 );
    // merges 2 linked lists of binomial trees and sorts the trees by increasing degree
 
    Node * mergeListsByDeg( Node * head1, Node * head2 );
    // reverses a linked list
 
    Node * reverseList( Node * head );
    // links root of tree1 to root of tree2 (tree1 becomes child of tree2)
    Node * linkTreeToTree( Node * root1, Node * root2 );
 
};
 
template < typename T, typename Comparator >
BinomialHeap < T, Comparator >::~BinomialHeap() {
    deleteTreeList( m_head );
}
 
template < typename T, typename Comparator >
void BinomialHeap < T, Comparator >::deleteTreeList( Node * head ) {
    while (head != nullptr) {
        Node * sibling = head->sibling;
        deleteTreeList( head->child );
        delete head;
        head = sibling;
    }
}
 
template < typename T, typename Comparator >
void BinomialHeap < T, Comparator >::insert( const T & value ) {
    Node * newNode = new Node( value, 0, nullptr, nullptr, nullptr );
 
    m_head = mergeHeaps( m_head, newNode ); // merge the current heap with the newNode,
     // as if the newNode was a single-element heap
    m_size++;
}
 
template< typename T, typename Comparator >
T BinomialHeap< T, Comparator >::extractMax() {
    if ( m_size == 0 )
        throw std::out_of_range ( "Heap is empty." );
 
    Node * * ptrToMax = searchMax( &m_head ); // find the node with maximum value
    Node * max = *ptrToMax;
 
    *ptrToMax = max->sibling; // disconnect it from the linked list
 
    Node * chlHead = reverseList( max->child ); // merge them with the heap in reversed order
    m_head = mergeHeaps( this->m_head, chlHead );
 
    m_size--;
    T maxVal = max->value;
    delete max; // extract the value from node and return it
    return maxVal;
}
 
template < typename T, typename Comparator >
void BinomialHeap < T, Comparator >::mergeWith( BinomialHeap< 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");
 
    this->m_head = mergeHeaps( this->m_head, that.m_head ); // move the other heap into this heap
    that.m_head = nullptr;
 
    this->m_size += that.m_size;
    that.m_size = 0;
}
 
template < typename T, typename Comparator >
typename BinomialHeap < T, Comparator >::Node * * BinomialHeap< T, Comparator >::searchMax( Node * * head ) const {
    Node * max = *head, * * ptrToMax = head;
    for (Node * actual = * head, * prev = nullptr; actual != nullptr; prev = actual, actual = actual->sibling) {
        if ( m_comparator ( max->value, actual->value ) ) {
            max = actual;
            ptrToMax = &prev->sibling;
        }
    }
    return ptrToMax;
}
 
template < typename T, typename Comparator >
typename BinomialHeap < T, Comparator >::Node * BinomialHeap< T, Comparator >::mergeHeaps( Node * head1, Node * head2 ) {
    if ( ! head1 )
        return head2;
 
    if ( ! head2 )
        return head1;
 
    head1 = mergeListsByDeg( head1, head2 ); // first, merge the lists of trees by their degrees
 
    Node * actual = head1;
    Node * * toLink = & head1;
    while (actual->sibling) {
        Node * next = actual->sibling;
 
        if (actual->degree != next->degree || (next->sibling && next->sibling->degree == actual->degree)) {
            toLink = &actual->sibling; // not merging trees with same degree
            actual = next; // or postponing the merge by 1 iteration
        } else if ( ! m_comparator ( actual->value, next->value ) ) {
            actual->sibling = next->sibling; // merging 2 binomial trees with same degree
            actual = linkTreeToTree( next, actual ); // 'next' becomes child of 'actual'
        } else {
            *toLink = next; // merging 2 binomial trees with same degree
            actual = linkTreeToTree( actual, next ); // 'actual' becomes child of 'next'
        }
    }
 
    return head1;
}
 
template < typename T, typename Comparator >
typename BinomialHeap < T, Comparator >::Node * BinomialHeap< T, Comparator >::mergeListsByDeg( Node * head1, Node * head2 ) {
    Node * newHead = nullptr;
    Node * * toLink = &newHead;
    while (head1 && head2) {
        if (head1->degree < head2->degree) {
            *toLink = head1; // linking node from first list
            toLink = &head1->sibling; // and moving first pointer
            head1 = head1->sibling;
        } else {
            *toLink = head2; // linking node from second list
            toLink = &head2->sibling; // and moving second pointer
            head2 = head2->sibling;
        }
    }
    if (!head1)
        *toLink = head2; // list1 ended, link the rest of list2
    else
        *toLink = head1; // list2 ended, link the rest of list1
 
    return newHead;
}
 
template < typename T, typename Comparator >
typename BinomialHeap < T, Comparator >::Node * BinomialHeap< T, Comparator >::reverseList( Node * head ) {
    Node * prev = nullptr;
 
    while (head) {
        Node * next = head->sibling;
        head->sibling = prev;
        prev = head;
        head = next;
    }
 
    return prev;
}
 
template < typename T, typename Comparator >
typename BinomialHeap < T, Comparator >::Node * BinomialHeap< T, Comparator >::linkTreeToTree( Node * root1, Node * root2 ) {
    root1->parent = root2;
    root1->sibling = root2->child;
    root2->child = root1;
    root2->degree++;
 
    return root2;
}
 
} /* namespace alib */