Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <shogun/lib/FibonacciHeap.h>
00013
00014 using namespace shogun;
00015
00016 CFibonacciHeap::CFibonacciHeap()
00017 {
00018 min_root = NULL;
00019
00020 max_num_nodes = 0;
00021 nodes = NULL;
00022 Dn = 0;
00023
00024 num_nodes = 0;
00025 num_trees = 0;
00026 }
00027
00028 CFibonacciHeap::CFibonacciHeap(int32_t capacity)
00029 {
00030 min_root = NULL;
00031
00032 max_num_nodes = capacity;
00033 nodes = SG_MALLOC(FibonacciHeapNode* , max_num_nodes);
00034 for(int32_t i = 0; i < max_num_nodes; i++)
00035 {
00036 nodes[i] = new FibonacciHeapNode;
00037 clear_node(i);
00038 }
00039
00040 Dn = 1 + (int32_t)(CMath::log2(max_num_nodes));
00041 A = SG_MALLOC(FibonacciHeapNode* , Dn);
00042 for(int32_t i = 0; i < Dn; i++)
00043 {
00044 A[i] = NULL;
00045 }
00046
00047 num_nodes = 0;
00048 num_trees = 0;
00049 }
00050
00051 CFibonacciHeap::~CFibonacciHeap()
00052 {
00053 for(int32_t i = 0; i < max_num_nodes; i++)
00054 {
00055 if(nodes[i] != NULL)
00056 delete nodes[i];
00057 }
00058 SG_FREE(nodes);
00059 SG_FREE(A);
00060 }
00061
00062 void CFibonacciHeap::insert(int32_t index, float64_t key)
00063 {
00064 if(index >= max_num_nodes || index < 0)
00065 return;
00066
00067 if(nodes[index]->index != -1)
00068 return;
00069
00070
00071 nodes[index]->child = NULL;
00072 nodes[index]->parent = NULL;
00073
00074 nodes[index]->rank = 0;
00075 nodes[index]->index = index;
00076 nodes[index]->key = key;
00077 nodes[index]->marked = false;
00078
00079 add_to_roots(nodes[index]);
00080 num_nodes++;
00081 }
00082
00083 int32_t CFibonacciHeap::extract_min(float64_t &ret_key)
00084 {
00085 FibonacciHeapNode *min_node;
00086 FibonacciHeapNode *child, *next_child;
00087
00088 int32_t result;
00089
00090 if(num_nodes == 0)
00091 return -1;
00092
00093 min_node = min_root;
00094 if(min_node == NULL)
00095 return -1;
00096
00097 child = min_node->child;
00098 while(child != NULL && child->parent != NULL)
00099 {
00100 next_child = child->right;
00101
00102
00103 child->left->right = child->right;
00104 child->right->left = child->left;
00105
00106 add_to_roots(child);
00107
00108
00109 child = next_child;
00110 }
00111
00112
00113 min_node->left->right = min_node->right;
00114 min_node->right->left = min_node->left;
00115
00116 num_trees--;
00117
00118 if(min_node == min_node->right)
00119 {
00120 min_root = NULL;
00121 }
00122 else
00123 {
00124 min_root = min_node->right;
00125 consolidate();
00126 }
00127
00128 result = min_node->index;
00129 ret_key = min_node->key;
00130 clear_node(result);
00131
00132 num_nodes--;
00133
00134 return result;
00135 }
00136
00137 void CFibonacciHeap::clear()
00138 {
00139 min_root = NULL;
00140
00141
00142 for(int32_t i = 0; i < max_num_nodes; i++)
00143 {
00144 clear_node(i);
00145 }
00146
00147 num_nodes = 0;
00148 num_trees = 0;
00149 }
00150
00151 int32_t CFibonacciHeap::get_key(int32_t index, float64_t &ret_key)
00152 {
00153 if(index >= max_num_nodes || index < 0)
00154 return -1;
00155 if(nodes[index]->index == -1)
00156 return -1;
00157
00158 int32_t result = nodes[index]->index;
00159 ret_key = nodes[index]->key;
00160
00161 return result;
00162 }
00163
00164 void CFibonacciHeap::decrease_key(int32_t index, float64_t key)
00165 {
00166 FibonacciHeapNode* parent;
00167
00168 if(index >= max_num_nodes || index < 0)
00169 return;
00170 if(nodes[index]->index == -1)
00171 return;
00172 if(key > nodes[index]->key)
00173 return;
00174
00175
00176 nodes[index]->key = key;
00177
00178 parent = nodes[index]->parent;
00179
00180 if(parent != NULL && nodes[index]->key < parent->key)
00181 {
00182 cut(nodes[index], parent);
00183 cascading_cut(parent);
00184 }
00185
00186 if(nodes[index]->key < min_root->key)
00187 min_root = nodes[index];
00188 }
00189
00190
00191 void CFibonacciHeap::add_to_roots(FibonacciHeapNode *up_node)
00192 {
00193 if(min_root == NULL)
00194 {
00195
00196 min_root = up_node;
00197
00198 up_node->left = up_node;
00199 up_node->right = up_node;
00200 }
00201 else
00202 {
00203
00204 up_node->right = min_root->right;
00205 up_node->left = min_root;
00206
00207 up_node->left->right = up_node;
00208 up_node->right->left = up_node;
00209
00210
00211 if(up_node->key < min_root->key)
00212 {
00213 min_root = up_node;
00214 }
00215 }
00216
00217 up_node->parent = NULL;
00218 num_trees++;
00219 }
00220
00221 void CFibonacciHeap::consolidate()
00222 {
00223 FibonacciHeapNode *x, *y, *w;
00224 int32_t d;
00225
00226 for(int32_t i = 0; i < Dn; i++)
00227 {
00228 A[i] = NULL;
00229 }
00230
00231 min_root->left->right = NULL;
00232 min_root->left = NULL;
00233 w = min_root;
00234
00235 do
00236 {
00237 x = w;
00238 d = x->rank;
00239 w = w->right;
00240
00241 while(A[d] != NULL)
00242 {
00243 y = A[d];
00244
00245 if(y->key < x->key)
00246 {
00247 FibonacciHeapNode *temp;
00248
00249 temp = y;
00250 y = x;
00251 x = temp;
00252 }
00253
00254 link_nodes(y, x);
00255
00256 A[d] = NULL;
00257 d++;
00258 }
00259 A[d] = x;
00260 }
00261 while(w != NULL);
00262
00263 min_root = NULL;
00264 num_trees = 0;
00265
00266 for(int32_t i = 0; i < Dn; i++)
00267 {
00268 if(A[i] != NULL)
00269 {
00270 A[i]->marked = false;
00271 add_to_roots(A[i]);
00272 }
00273 }
00274 }
00275
00276 void CFibonacciHeap::link_nodes(FibonacciHeapNode *y, FibonacciHeapNode *x)
00277 {
00278 if(y->right != NULL)
00279 y->right->left = y->left;
00280 if(y->left != NULL)
00281 y->left->right = y->right;
00282
00283 num_trees--;
00284
00285 y->left = y;
00286 y->right = y;
00287
00288 y->parent = x;
00289
00290 if(x->child == NULL)
00291 {
00292 x->child = y;
00293 }
00294 else
00295 {
00296 y->left = x->child;
00297 y->right = x->child->right;
00298
00299 x->child->right = y;
00300 y->right->left = y;
00301 }
00302
00303 x->rank++;
00304
00305 y->marked = false;
00306 }
00307
00308 void CFibonacciHeap::clear_node(int32_t index)
00309 {
00310 nodes[index]->parent = NULL;
00311 nodes[index]->child = NULL;
00312 nodes[index]->left = NULL;
00313 nodes[index]->right = NULL;
00314
00315 nodes[index]->rank = 0;
00316 nodes[index]->index = -1;
00317 nodes[index]->key = 0;
00318
00319 nodes[index]->marked = false;
00320 }
00321
00322 void CFibonacciHeap::cut(FibonacciHeapNode *child, FibonacciHeapNode *parent)
00323 {
00324 if(parent->child == child)
00325 parent->child = child->right;
00326
00327 if(parent->child == child)
00328 parent->child = NULL;
00329
00330 parent->rank--;
00331
00332 child->left->right = child->right;
00333 child->right->left = child->left;
00334 child->marked = false;
00335
00336 add_to_roots(child);
00337 }
00338
00339 void CFibonacciHeap::cascading_cut(FibonacciHeapNode *tree)
00340 {
00341 FibonacciHeapNode *temp;
00342
00343 temp = tree->parent;
00344 if(temp != NULL)
00345 {
00346 if(!tree->marked)
00347 {
00348 tree->marked = true;
00349 }
00350 else
00351 {
00352 cut(tree, temp);
00353 cascading_cut(temp);
00354 }
00355 }
00356 }
00357
00358 void CFibonacciHeap::debug_print()
00359 {
00360 SG_SPRINT("%d %d\n", num_trees, num_nodes);
00361 for(int32_t i = 0; i < max_num_nodes; i++)
00362 {
00363 if(nodes[i]->index == -1)
00364 {
00365 SG_SPRINT("None\n");
00366 }
00367 else
00368 {
00369 SG_SPRINT("%f\n",nodes[i]->key);
00370 }
00371 }
00372 }