Slicer
5.2
Slicer is a multi-platform, free and open source software package for visualization and medical image computing
|
#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 () |
FibHeap::FibHeap | ( | ) |
|
virtual |
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).
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.
FibHeapNode* FibHeap::ExtractMin | ( | ) |
ExtractMin() - O(n) worst-case actual; O(lg n) amortized.
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.
|
inline |
void FibHeap::Print | ( | FibHeapNode * | Tree = nullptr , |
FibHeapNode * | theParent = nullptr |
||
) |
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.
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.