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