PairingHeap.h

Go to the documentation of this file.

 
#ifndef PAIRING_HEAP_H_
#define PAIRING_HEAP_H_
#include <stdlib.h>
#include <fstream>
// Pairing heap class
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// PairNode & insert( x ) --> Insert x
// deleteMin( minItem )   --> Remove (and optionally return) smallest item
// T findMin( )  --> Return smallest item
// bool isEmpty( )        --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Throws Underflow as warranted
 
 
// Node and forward declaration because g++ does
// not understand nested classes.
template <class T> 
class PairingHeap;
 
template <class T>
std::ostream& operator<< (std::ostream &os,const PairingHeap<T> &b);
 
template <class T>
class PairNode
{
        friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
        T   element;
        PairNode    *leftChild;
        PairNode    *nextSibling;
        PairNode    *prev;
 
        PairNode( const T & theElement ) :
                element( theElement ),
                leftChild(nullptr), nextSibling(nullptr), prev(nullptr)
        { }
        friend class PairingHeap<T>;
};
 
template <class T>
class PairingHeap
{
        friend std::ostream& operator<< <T>(std::ostream &os,const PairingHeap<T> &b);
public:
        PairingHeap( bool (*lessThan)(T const &lhs, T const &rhs) );
        ~PairingHeap( );
 
        bool isEmpty( ) const;
 
        PairNode<T> *insert( const T & x );
        const T & findMin( ) const;
        void deleteMin( );
        void makeEmpty( );
        void merge( PairingHeap<T> *rhs )
        {       
                PairNode<T> *broot=rhs->getRoot();
                if (root == nullptr) {
                        if(broot != nullptr) {
                                root = broot;
                        }
                } else {
                        compareAndLink(root, broot);
                }
        }
 
        PairingHeap(const PairingHeap &rhs) = delete;
        PairingHeap(PairingHeap &&rhs) = delete;
        PairingHeap &operator=(const PairingHeap &rhs) = delete;
        PairingHeap &operator=(PairingHeap &&rhs) = delete;
protected:
        PairNode<T> * getRoot() {
                PairNode<T> *r=root;
                root=nullptr;
                return r;
        }
private:
        PairNode<T> *root;
        bool (*lessThan)(T const &lhs, T const &rhs);
        void reclaimMemory( PairNode<T> *t ) const;
        void compareAndLink( PairNode<T> * & first, PairNode<T> *second ) const;
        PairNode<T> * combineSiblings( PairNode<T> *firstSibling ) const;
};
 
#include "PairingHeap.cpp"
#endif