Slicer  5.0
Slicer is a multi-platform, free and open source software package for visualization and medical image computing
FibHeap.h
Go to the documentation of this file.
1 //***************************************************************************
2 // The Fibonacci heap implementation contained in FIBHEAP.H and FIBHEAP.CPP
3 // is Copyright (c) 1996 by John Boyer
4 //
5 // Once this Fibonacci heap implementation (the software) has been published
6 // by Dr. Dobb's Journal, permission to use and distribute the software is
7 // granted provided that this copyright notice remains in the source and
8 // and the author (John Boyer) is acknowledged in works that use this program.
9 //
10 // Every effort has been made to ensure that this implementation is free of
11 // errors. Nonetheless, the author (John Boyer) assumes no liability regarding
12 // your use of this software.
13 //
14 // The author would also be very glad to hear from anyone who uses the
15 // software or has any feedback about it.
16 // Email: jboyer@gulf.csc.uvic.ca
17 //***************************************************************************
18 
19 // exclude from VTK wrapping
20 #ifndef __VTK_WRAP__
21 
22 #ifndef FIBHEAP_H
23 #define FIBHEAP_H
24 
25 #include <cstdio>
26 #include <iostream>
27 
28 // type for cost function - single precision is enough
29 typedef float NodeKeyValueType;
30 
31 // type for storing a pixel index
32 // We could use 32-bit indices for images smaller than 4GB and 64-bit indices for larger images.
33 // However, >4GB images would require about 300GB RAM to store all the indices and distances,
34 // so for now we only support images smaller than 4GB.
35 typedef unsigned int NodeIndexType;
36 
37 // .NAME FibHeapNode - Fibonacci Heap Node Class
38 // .SECTION Description
39 //
40 // This class stores all data of a node in the Fibonacci heap and implements
41 // basic operations on nodes (comparison, assignment, etc.).
42 //
43 // In the original implementation of John Boyer FibHeapNode was a base class
44 // and the implementation was completed in a derived class
45 // However, virtual methods reduced performance by a few percent and the
46 // virtual method table added extra 8 bytes for the size of each node,
47 // which was significant when one node represented a voxel (and we had
48 // hundreds of millions of voxels in an image).
49 
51 {
52 public:
55 
56  inline FibHeapNode()
62  {
63  }
64 
65  ~FibHeapNode() = default;
66 
68  inline NodeIndexType GetIndexValue() { return m_Index; }
69  inline void SetIndexValue(NodeIndexType indexValue) { m_Index = indexValue; }
70 
73  inline NodeKeyValueType GetKeyValue() { return m_Key; }
74 
76  inline void operator =(NodeKeyValueType newKeyVal)
77  {
78  m_Key = newKeyVal;
79  }
80 
82  inline void operator =(FibHeapNode& RHS)
83  {
84  m_Key = RHS.m_Key;
85  }
86 
88  inline bool operator ==(FibHeapNode& RHS)
89  {
90  return m_Key == RHS.m_Key;
91  }
92 
94  inline bool operator <(FibHeapNode& RHS)
95  {
96  return m_Key < RHS.m_Key;
97  }
98 
99  void Print()
100  {
101  std::cout << m_Key;
102  }
103 
108  short m_Degree{0};
109  bool m_Mark{false};
110 
113 };
114 
115 // .NAME FibHeap - Fibonacci Heap Class
116 // .SECTION Description
117 //
118 // This class implements a performance-optimized heap data structure.
119 // Using amortized analysis, the asymptotically fastest heap
120 // data structure is the Fibonacci heap. The constants are a little
121 // high so the real speed gain will not be seen until larger data sets
122 // are required, but in most cases, if the data set is small, then the
123 // run-time will be negligible anyway.
124 //
125 // FibHeap class can then be used to Insert(), ExtractMin(), etc.,
126 // instances of FibHeapNode class.
127 
129 
130 class FibHeap
131 {
132 public:
133  FibHeap();
134  virtual ~FibHeap();
135 
142  void SetHeapNodes(FibHeapNode* heapNodes);
143 
153  void Insert(FibHeapNode *NewNode);
154 
156  void Union(FibHeap *OtherHeap);
157 
160  {
161  return m_MinRoot;
162  }
163 
166 
171  int DecreaseKey(FibHeapNode* theNode, NodeKeyValueType keyValue);
172 
178  int Delete(FibHeapNode *theNode);
179 
180  inline bool IsEmpty()
181  {
182  return (m_MinRoot == nullptr);
183  }
184 
185  // Extra utility functions
186  long GetNumNodes()
187  {
188  return m_NumNodes;
189  };
190  long GetNumTrees()
191  {
192  return m_NumTrees;
193  };
195  {
196  return m_NumMarkedNodes;
197  };
198 
204  void Print(FibHeapNode *Tree = nullptr, FibHeapNode *theParent=nullptr);
205 
206 private:
207  // Internal functions that help to implement the Standard Operations
208  inline void Exchange(FibHeapNode* &N1, FibHeapNode* &N2)
209  {
210  FibHeapNode *Temp;
211  Temp = N1;
212  N1 = N2;
213  N2 = Temp;
214  }
215 
216  // Internal function that reorganizes heap as part of an ExtractMin().
217  // We must find new minimum in heap, which could be anywhere along the
218  // root list. The search could be O(n) since all nodes could be on
219  // the root list. So, we reorganize the tree into more of a binomial forest
220  // structure, and then find the new minimum on the consolidated O(lg n) sized
221  // root list, and in the process set each m_Parent pointer to nullptr, and count
222  // the number of resulting subtrees.
223  //
224  // Note that after a list of n inserts, there will be n nodes on the root
225  // list, so the first ExtractMin() will be O(n) regardless of whether or
226  // not we consolidate. However, the consolidation causes subsequent
227  // ExtractMin() operations to be O(lg n). Furthermore, the extra cost of
228  // the first ExtractMin() is covered by the higher amortized cost of
229  // Insert(), which is the real governing factor in how costly the first
230  // ExtractMin() will be.
231  void Consolidate();
232 
233  // The node y is removed from the root list and becomes a subtree of node x.
234  void Link(FibHeapNode *, FibHeapNode *);
235  void AddToRootList(FibHeapNode *);
236 
237  // Remove node x from the child list of its parent node y
238  void Cut(FibHeapNode *, FibHeapNode *);
239 
240  // Cuts each node in parent list, putting successive ancestor nodes on the
241  // root list until we either arrive at the root list or until we find an
242  // ancestor that is unmarked. When a mark is set (which only happens during
243  // a cascading cut), it means that one child subtree has been lost; if a
244  // second subtree is lost later during another cascading cut, then we move
245  // the node to the root list so that it can be re-balanced on the next
246  // consolidate.
247  void CascadingCut(FibHeapNode *);
248 
249  inline FibHeapNode* HeapNodeFromIndex(NodeIndexType index)
250  {
251  return index == FibHeapNode::NullNodeIndex ? nullptr : m_HeapNodes + index;
252  }
253 
254  FibHeapNode* m_MinRoot;
255  long m_NumNodes;
256  long m_NumTrees;
257  long m_NumMarkedNodes;
258  FibHeapNode* m_HeapNodes; // array containing all the heap nodes
259 
260 };
261 
262 #endif /* FIBHEAP_H */
263 
264 #endif //__VTK_WRAP__
NodeIndexType m_Left
Definition: FibHeap.h:104
virtual ~FibHeap()
bool operator<(FibHeapNode &RHS)
Compare key value.
Definition: FibHeap.h:94
void Print(FibHeapNode *Tree=nullptr, FibHeapNode *theParent=nullptr)
int Delete(FibHeapNode *theNode)
NodeIndexType m_Parent
Definition: FibHeap.h:106
static const NodeIndexType NullNodeIndex
Definition: FibHeap.h:53
void SetIndexValue(NodeIndexType indexValue)
Definition: FibHeap.h:69
void Union(FibHeap *OtherHeap)
Union() - O(1) actual; O(1) amortized.
FibHeapNode * ExtractMin()
ExtractMin() - O(n) worst-case actual; O(lg n) amortized.
bool IsEmpty()
Definition: FibHeap.h:180
bool m_Mark
Definition: FibHeap.h:109
float NodeKeyValueType
Definition: FibHeap.h:29
void Print()
Definition: FibHeap.h:99
NodeIndexType m_Index
Definition: FibHeap.h:112
long GetNumMarkedNodes()
Definition: FibHeap.h:194
~FibHeapNode()=default
unsigned int NodeIndexType
Definition: FibHeap.h:35
NodeKeyValueType m_Key
Definition: FibHeap.h:111
void Insert(FibHeapNode *NewNode)
NodeIndexType GetIndexValue()
Index stores this node&#39;s location in the node array.
Definition: FibHeap.h:68
short m_Degree
Definition: FibHeap.h:108
bool operator==(FibHeapNode &RHS)
Compare key value.
Definition: FibHeap.h:88
long GetNumTrees()
Definition: FibHeap.h:190
FibHeapNode()
Definition: FibHeap.h:56
void operator=(NodeKeyValueType newKeyVal)
Set key value (that the nodes are sorted based on)
Definition: FibHeap.h:76
static const NodeKeyValueType NegativeInfinity
Definition: FibHeap.h:54
NodeIndexType m_Right
Definition: FibHeap.h:105
NodeKeyValueType GetKeyValue()
Definition: FibHeap.h:73
int DecreaseKey(FibHeapNode *theNode, NodeKeyValueType keyValue)
FibHeapNode * Minimum()
Minimum - O(1) actual; O(1) amortized.
Definition: FibHeap.h:159
void SetHeapNodes(FibHeapNode *heapNodes)
NodeIndexType m_Child
Definition: FibHeap.h:107
long GetNumNodes()
Definition: FibHeap.h:186