00001 #ifndef FIBHEAP_H
00002 #define FIBHEAP_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #define OK 0
00023 #define NOTOK -1
00024
00025
00026
00027
00028
00029 class FibHeap;
00030
00032 class FibHeapNode
00033 {
00034 friend class FibHeap;
00035
00036 FibHeapNode *Left, *Right, *Parent, *Child;
00037 short Degree, Mark, NegInfinityFlag;
00038
00039 protected:
00040
00041 inline int FHN_Cmp(FibHeapNode& RHS){
00042 if (NegInfinityFlag)
00043 return RHS.NegInfinityFlag ? 0 : -1;
00044 return RHS.NegInfinityFlag ? 1 : 0;
00045 }
00046 inline void FHN_Assign(FibHeapNode& RHS){
00047 NegInfinityFlag = RHS.NegInfinityFlag;
00048 }
00049
00050 public:
00051
00052 FibHeapNode(){
00053 Left = Right = Parent = Child = NULL;
00054 Degree = Mark = NegInfinityFlag = 0;
00055 }
00056 virtual ~FibHeapNode();
00057
00058 virtual void operator =(FibHeapNode& RHS);
00059 virtual int operator ==(FibHeapNode& RHS);
00060 virtual int operator <(FibHeapNode& RHS);
00061
00062 virtual void Print();
00063 };
00064
00065
00066
00067
00068
00070 class FibHeap
00071 {
00072 FibHeapNode *MinRoot;
00073 long NumNodes, NumTrees, NumMarkedNodes;
00074
00075 int HeapOwnershipFlag;
00076
00077 public:
00078
00079 FibHeap();
00080 virtual ~FibHeap();
00081
00082
00083
00084 void Insert(FibHeapNode *NewNode);
00085 void Union(FibHeap *OtherHeap);
00086
00087 inline FibHeapNode *Minimum(){
00088 return MinRoot;
00089 }
00090 FibHeapNode *ExtractMin();
00091
00092 int DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey);
00093 int Delete(FibHeapNode *theNode);
00094
00095
00096
00097 int GetHeapOwnership() { return HeapOwnershipFlag; };
00098 void SetHeapOwnership() { HeapOwnershipFlag = 1; };
00099 void ClearHeapOwnership() { HeapOwnershipFlag = 0; };
00100
00101 long GetNumNodes() { return NumNodes; };
00102 long GetNumTrees() { return NumTrees; };
00103 long GetNumMarkedNodes() { return NumMarkedNodes; };
00104
00105 void Print(FibHeapNode *Tree = NULL, FibHeapNode *theParent=NULL);
00106
00107 private:
00108
00109
00110
00111 inline void _Exchange(FibHeapNode* &N1, FibHeapNode* &N2){
00112 FibHeapNode *Temp;
00113
00114 Temp = N1;
00115 N1 = N2;
00116 N2 = Temp;
00117 }
00118
00119 void _Consolidate();
00120 void _Link(FibHeapNode *, FibHeapNode *);
00121 void _AddToRootList(FibHeapNode *);
00122 void _Cut(FibHeapNode *, FibHeapNode *);
00123 void _CascadingCut(FibHeapNode *);
00124 };
00125
00126 #endif