?? fibheap.h
字號:
#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
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -