14 using namespace shogun;
16 CFibonacciHeap::CFibonacciHeap()
28 CFibonacciHeap::CFibonacciHeap(int32_t capacity)
32 max_num_nodes = capacity;
33 nodes =
SG_MALLOC(FibonacciHeapNode* , max_num_nodes);
34 for(int32_t i = 0; i < max_num_nodes; i++)
36 nodes[i] =
new FibonacciHeapNode;
42 for(int32_t i = 0; i < Dn; i++)
51 CFibonacciHeap::~CFibonacciHeap()
53 for(int32_t i = 0; i < max_num_nodes; i++)
62 void CFibonacciHeap::insert(int32_t index,
float64_t key)
64 if(index >= max_num_nodes || index < 0)
67 if(nodes[index]->index != -1)
71 nodes[index]->child = NULL;
72 nodes[index]->parent = NULL;
74 nodes[index]->rank = 0;
75 nodes[index]->index = index;
76 nodes[index]->key = key;
77 nodes[index]->marked =
false;
79 add_to_roots(nodes[index]);
83 int32_t CFibonacciHeap::extract_min(
float64_t &ret_key)
85 FibonacciHeapNode *min_node;
86 FibonacciHeapNode *child, *next_child;
97 child = min_node->child;
98 while(child != NULL && child->parent != NULL)
100 next_child = child->right;
103 child->left->right = child->right;
104 child->right->left = child->left;
113 min_node->left->right = min_node->right;
114 min_node->right->left = min_node->left;
118 if(min_node == min_node->right)
124 min_root = min_node->right;
128 result = min_node->index;
129 ret_key = min_node->key;
137 void CFibonacciHeap::clear()
142 for(int32_t i = 0; i < max_num_nodes; i++)
151 int32_t CFibonacciHeap::get_key(int32_t index,
float64_t &ret_key)
153 if(index >= max_num_nodes || index < 0)
155 if(nodes[index]->index == -1)
158 int32_t result = nodes[index]->index;
159 ret_key = nodes[index]->key;
164 void CFibonacciHeap::decrease_key(int32_t index,
float64_t key)
166 FibonacciHeapNode* parent;
168 if(index >= max_num_nodes || index < 0)
170 if(nodes[index]->index == -1)
172 if(key > nodes[index]->key)
176 nodes[index]->key = key;
178 parent = nodes[index]->parent;
180 if(parent != NULL && nodes[index]->key < parent->key)
182 cut(nodes[index], parent);
183 cascading_cut(parent);
186 if(nodes[index]->key < min_root->key)
187 min_root = nodes[index];
191 void CFibonacciHeap::add_to_roots(FibonacciHeapNode *up_node)
198 up_node->left = up_node;
199 up_node->right = up_node;
204 up_node->right = min_root->right;
205 up_node->left = min_root;
207 up_node->left->right = up_node;
208 up_node->right->left = up_node;
211 if(up_node->key < min_root->key)
217 up_node->parent = NULL;
221 void CFibonacciHeap::consolidate()
223 FibonacciHeapNode *x, *y, *w;
226 for(int32_t i = 0; i < Dn; i++)
231 min_root->left->right = NULL;
232 min_root->left = NULL;
247 FibonacciHeapNode *temp;
266 for(int32_t i = 0; i < Dn; i++)
270 A[i]->marked =
false;
276 void CFibonacciHeap::link_nodes(FibonacciHeapNode *y, FibonacciHeapNode *x)
279 y->right->left = y->left;
281 y->left->right = y->right;
297 y->right = x->child->right;
308 void CFibonacciHeap::clear_node(int32_t index)
310 nodes[index]->parent = NULL;
311 nodes[index]->child = NULL;
312 nodes[index]->left = NULL;
313 nodes[index]->right = NULL;
315 nodes[index]->rank = 0;
316 nodes[index]->index = -1;
317 nodes[index]->key = 0;
319 nodes[index]->marked =
false;
322 void CFibonacciHeap::cut(FibonacciHeapNode *child, FibonacciHeapNode *parent)
324 if(parent->child == child)
325 parent->child = child->right;
327 if(parent->child == child)
328 parent->child = NULL;
332 child->left->right = child->right;
333 child->right->left = child->left;
334 child->marked =
false;
339 void CFibonacciHeap::cascading_cut(FibonacciHeapNode *tree)
341 FibonacciHeapNode *temp;
358 void CFibonacciHeap::debug_print()
360 SG_SPRINT(
"%d %d\n", num_trees, num_nodes);
361 for(int32_t i = 0; i < max_num_nodes; i++)
363 if(nodes[i]->index == -1)