FibHeap Class Reference

#include <Modules/Loadable/Segmentations/Logic/FibHeap.h>

Public Member Functions
int	DecreaseKey (FibHeapNode *theNode, NodeKeyValueType keyValue)
int	Delete (FibHeapNode *theNode)
FibHeapNode *	ExtractMin ()
	ExtractMin() - O(n) worst-case actual; O(lg n) amortized. More...
	FibHeap ()
long	GetNumMarkedNodes ()
long	GetNumNodes ()
long	GetNumTrees ()
void	Insert (FibHeapNode *NewNode)
bool	IsEmpty ()
FibHeapNode *	Minimum ()
	Minimum - O(1) actual; O(1) amortized. More...
void	Print (FibHeapNode *Tree=nullptr, FibHeapNode *theParent=nullptr)
void	SetHeapNodes (FibHeapNode *heapNodes)
void	Union (FibHeap *OtherHeap)
	Union() - O(1) actual; O(1) amortized. More...
virtual	~FibHeap ()

Detailed Description

Definition at line 130 of file FibHeap.h.

Constructor & Destructor Documentation

FibHeap()

FibHeap::FibHeap

(

)

~FibHeap()

virtual FibHeap::~FibHeap ( )

virtual

Member Function Documentation

DecreaseKey()

int FibHeap::DecreaseKey	(	FibHeapNode *	theNode,
		NodeKeyValueType	keyValue
	)

DecreaseKey() - O(lg n) actual; O(1) amortized

The O(lg n) actual cost stems from the fact that the depth, and therefore the number of ancestor parents, is bounded by O(lg n).

Delete()

int FibHeap::Delete

(

FibHeapNode *

theNode

)

Delete() - O(lg n) amortized; ExtractMin() dominates

Notice that if we don't own the heap nodes, then we clear the m_NegInfinityFlag on the deleted node. Presumably, the programmer will be reusing the node.

ExtractMin()

FibHeapNode* FibHeap::ExtractMin

(

)

ExtractMin() - O(n) worst-case actual; O(lg n) amortized.

GetNumMarkedNodes()

long FibHeap::GetNumMarkedNodes ( )

inline

Definition at line 194 of file FibHeap.h.

GetNumNodes()

long FibHeap::GetNumNodes ( )

inline

Definition at line 186 of file FibHeap.h.

GetNumTrees()

long FibHeap::GetNumTrees ( )

inline

Definition at line 190 of file FibHeap.h.

Insert()

void FibHeap::Insert

(

FibHeapNode *

NewNode

)

Insert() - O(1) actual; O(2) amortized

I am using O(2) here to indicate that although Insert() is constant time, its amortized rating is more costly because some of the work of inserting is done by other operations such as ExtractMin(), which is where tree-balancing occurs.

The child pointer is deliberately not set to nullptr because Insert() is also used internally to help put whole trees onto the root list.

IsEmpty()

bool FibHeap::IsEmpty ( )

inline

Definition at line 180 of file FibHeap.h.

Minimum()

FibHeapNode* FibHeap::Minimum ( )

inline

Minimum - O(1) actual; O(1) amortized.

Definition at line 159 of file FibHeap.h.

Print()

void FibHeap::Print	(	FibHeapNode *	Tree = nullptr,
		FibHeapNode *	theParent = nullptr
	)

Print()

Used internally for debugging purposes. The function prints the key value for each node along the root list, then it calls itself on each child list.

SetHeapNodes()

void FibHeap::SetHeapNodes

(

FibHeapNode *

heapNodes

)

Set array that stores all nodes. The array is not owned by this object and must remain valid while this object is used. Nodes are stored in an array to allow referencing them using a 32-bit index instead of a 64-bit pointer. Since each node stores 4 pointer/index, this saves 16 bytes per node, which is very significant when e.g., one node corresponds to an image voxel and the image contains hundreds of millions of voxels.

Union()

void FibHeap::Union

(

FibHeap *

OtherHeap

)

Union() - O(1) actual; O(1) amortized.

---

The documentation for this class was generated from the following file:

• Modules/Loadable/Segmentations/Logic/FibHeap.h