#include "pairheap.h"
        #include "fatal.h"
        #include <stdlib.h>

        struct PairNode
        {
            ElementType Element;
            Position    LeftChild;
            Position    NextSibling;
            Position    Prev;
        };

        #define MaxSiblings 1000

        Position CompareAndLink( Position First, Position Second );
        PairHeap CombineSiblings( Position FirstSibling );


        PairHeap
        Initialize( void )
        {
            return NULL;
        }

        PairHeap
        MakeEmpty( PairHeap H )
        {
            if( H != NULL )
            {
                MakeEmpty( H->LeftChild );
                MakeEmpty( H->NextSibling );
                free( H );
            }
            return NULL;
        }

/* START: fig12_54.txt */
        /* Insert Item into pairing heap H */
        /* Return resulting pairing heap */
        /* A pointer to the newly allocated node */
        /* is passed back by reference and accessed as *Loc */

        PairHeap
        Insert( ElementType Item, PairHeap H, Position *Loc )
        {
            Position NewNode;

            NewNode = malloc( sizeof( struct PairNode ) );
            if( NewNode == NULL )
                FatalError( "Out of space!!!" );
            NewNode->Element = Item;
            NewNode->LeftChild = NewNode->NextSibling = NULL;
            NewNode->Prev = NULL;

            *Loc = NewNode;
            if( H == NULL )
                return NewNode;
            else
                return CompareAndLink( H, NewNode );
        }


        /* Lower item in Position P by Delta */

        PairHeap
        DecreaseKey( Position P, ElementType Delta, PairHeap H )
        {
            if( Delta < 0 )
                Error( "DecreaseKey called with negative Delta" );

            P->Element -= Delta;
            if( P == H )
                return H;

            if( P->NextSibling != NULL )
                P->NextSibling->Prev = P->Prev;
            if( P->Prev->LeftChild == P )
                P->Prev->LeftChild = P->NextSibling;
            else
                P->Prev->NextSibling = P->NextSibling;

            P->NextSibling = NULL;
            return CompareAndLink( H, P );
        }
/* END */


/* START: fig12_55.txt */
        PairHeap
        DeleteMin( ElementType *MinItem, PairHeap H )
        {
            Position NewRoot = NULL;

            if( IsEmpty( H ) )
                Error( "Pairing heap is empty!" );
            else
            {
                *MinItem = H->Element;
                if( H->LeftChild != NULL )
                    NewRoot = CombineSiblings( H->LeftChild );
                free( H );
            }
            return NewRoot;
        }
/* END */

/* START: fig12_53.txt */
        /* This is the basic operation to maintain order */
        /* Links First and Second together to satisfy heap order */
        /* Returns the resulting tree */
        /* First is assumed NOT NULL */
        /* First->NextSibling  MUST be NULL on entry */

        Position
        CompareAndLink( Position First, Position Second )
        {
            if( Second == NULL )
                return First;
            else
            if( First->Element <= Second->Element )
            {
                /* Attach Second as the leftmost child of First */
                Second->Prev = First;
                First->NextSibling = Second->NextSibling;
                if( First->NextSibling != NULL )
                    First->NextSibling->Prev = First;
                Second->NextSibling = First->LeftChild;
                if( Second->NextSibling != NULL )
                    Second->NextSibling->Prev = Second;
                First->LeftChild = Second;
                return First;
            }
            else
            {
                /* Attach First as the leftmost child of Second */
                Second->Prev = First->Prev;
                First->Prev = Second;
                First->NextSibling = Second->LeftChild;
                if( First->NextSibling != NULL )
                    First->NextSibling->Prev = First;
                Second->LeftChild = First;
                return Second;
            }
        }
/* END */

/* START: fig12_56.txt */
        /* Assumes FirstSibling is NOT NULL */

        PairHeap
        CombineSiblings( Position FirstSibling )
        {
            static Position TreeArray[ MaxSiblings ];
            int i, j, NumSiblings;

            /* If only one tree, return it */
            if( FirstSibling->NextSibling == NULL )
                return FirstSibling;

            /* Place each subtree in TreeArray */
            for( NumSiblings = 0; FirstSibling != NULL; NumSiblings++ )
            {
                TreeArray[ NumSiblings ] = FirstSibling;
                FirstSibling->Prev->NextSibling = NULL; /* Break links */
                FirstSibling = FirstSibling->NextSibling;
            }
            TreeArray[ NumSiblings ] = NULL;

            /* Combine the subtrees two at a time, */
            /* going left to right */
            for( i = 0; i + 1 < NumSiblings; i += 2 )
                TreeArray[ i ] = CompareAndLink(
                        TreeArray[ i ], TreeArray[ i + 1 ] );

            /* j has the result of the last CompareAndLink */
            /* If an odd number of trees, get the last one */
            j = i - 2;
            if( j == NumSiblings - 3 )
                TreeArray[ j ] = CompareAndLink(
                        TreeArray[ j ], TreeArray[ j + 2 ] );

            /* Now go right to left, merging last tree with */
            /* next to last. The result becomes the new last */
            for( ; j >= 2; j -= 2 )
                TreeArray[ j - 2 ] = CompareAndLink(
                        TreeArray[ j - 2 ],  TreeArray[ j ] );

            return TreeArray[ 0 ];
        }
/* END */

        ElementType
        FindMin( PairHeap H )
        {
            if( !IsEmpty( H ) )
                return H->Element;
            Error( "Priority Queue is Empty" );
            return 0;
        }

        int
        IsEmpty( PairHeap H )
        {
            return H == NULL;
        }

        int
        IsFull( PairHeap H )
        {
            return 0;   /* Never full */
        }

        void
        Destroy( PairHeap H )
        {
            MakeEmpty( H );
        }