#ifndef _FIBHEAP_H#define _FIBHEAP_H//***************************************************************************// The Fibonacci heap implementation contained in FIBHEAP.H and FIBHEAP.CPP// is Copyright (c) 1996 by John Boyer//// Once this Fibonacci heap implementation (the software) has been published// by Dr. Dobb's Journal, permission to use and distribute the software is// granted provided that this copyright notice remains in the source and// and the author (John Boyer) is acknowledged in works that use this program.//// Every effort has been made to ensure that this implementation is free of// errors.  Nonetheless, the author (John Boyer) assumes no liability regarding// your use of this software.//// The author would also be very glad to hear from anyone who uses the// software or has any feedback about it.// Email: jboyer@gulf.csc.uvic.ca//***************************************************************************#define OK      0#define NOTOK   -1//======================================================// Fibonacci Heap Node Class//======================================================class FibHeap;class FibHeapNode{friend class FibHeap;     FibHeapNode *Left, *Right, *Parent, *Child;     short Degree, Mark, NegInfinityFlag;protected:     inline int  FHN_Cmp(FibHeapNode& RHS);     inline void FHN_Assign(FibHeapNode& RHS);public:     inline  FibHeapNode();     virtual ~FibHeapNode();     virtual void operator =(FibHeapNode& RHS);     virtual int  operator ==(FibHeapNode& RHS);     virtual int  operator <(FibHeapNode& RHS);     virtual void Print();};//========================================================================// Fibonacci Heap Class//========================================================================class FibHeap{     FibHeapNode *MinRoot;     long NumNodes, NumTrees, NumMarkedNodes;     int HeapOwnershipFlag;public:     FibHeap();     virtual ~FibHeap();// The Standard Heap Operations     void Insert(FibHeapNode *NewNode);     void Union(FibHeap *OtherHeap);     inline FibHeapNode *Minimum();     FibHeapNode *ExtractMin();     int DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey);     int Delete(FibHeapNode *theNode);// Extra utility functions     int  GetHeapOwnership() { return HeapOwnershipFlag; };     void SetHeapOwnership() { HeapOwnershipFlag = 1; };     void ClearHeapOwnership() { HeapOwnershipFlag = 0; };     long GetNumNodes() { return NumNodes; };     long GetNumTrees() { return NumTrees; };     long GetNumMarkedNodes() { return NumMarkedNodes; };     void Print(FibHeapNode *Tree = NULL, FibHeapNode *theParent=NULL);private:// Internal functions that help to implement the Standard Operations     inline void _Exchange(FibHeapNode*&, FibHeapNode*&);     void _Consolidate();     void _Link(FibHeapNode *, FibHeapNode *);     void _AddToRootList(FibHeapNode *);     void _Cut(FibHeapNode *, FibHeapNode *);     void _CascadingCut(FibHeapNode *);};#endif