Slicer  4.11
Slicer is a multi-platform, free and open source software package for visualization and medical image computing
List of all members | Public Member Functions
FibHeap Class Reference

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

Public Member Functions

int DecreaseKey (FibHeapNode *theNode, NodeKeyValueType keyValue)
 
int Delete (FibHeapNode *theNode)
 
FibHeapNodeExtractMin ()
 ExtractMin() - O(n) worst-case actual; O(lg n) amortized. More...
 
 FibHeap ()
 
long GetNumMarkedNodes ()
 
long GetNumNodes ()
 
long GetNumTrees ()
 
void Insert (FibHeapNode *NewNode)
 
bool IsEmpty ()
 
FibHeapNodeMinimum ()
 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 133 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 197 of file FibHeap.h.

◆ GetNumNodes()

long FibHeap::GetNumNodes ( )
inline

Definition at line 189 of file FibHeap.h.

◆ GetNumTrees()

long FibHeap::GetNumTrees ( )
inline

Definition at line 193 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 183 of file FibHeap.h.

◆ Minimum()

FibHeapNode* FibHeap::Minimum ( )
inline

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

Definition at line 162 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: