Fibonacci heap
unknown
c_cpp
a year ago
9.6 kB
9
Indexable
// Fibonacci heap // patata0717 #include <stdbool.h> #include <stdio.h> #include <stdlib.h> // Node typedef struct sNode { int key; // value int degree; // number of child, LAZY(calculate while needed) bool mark; // mark if has lost child struct sNode *leftSib; struct sNode *rightSib; struct sNode *parent; struct sNode *child; } Node; Node* _CreateNode(int key); // constructor // FibonacciHeap typedef struct sFibonacciHeap { int n; // number of nodes Node *min; Node *rootList; } FibonacciHeap; FibonacciHeap* CreateFibonacciHeap(); // constructor Node* FindMin(FibonacciHeap* FH); // find mininum node Node* Insert(FibonacciHeap* FH, int key); // insert new node void _MergeWithDoublyList(FibonacciHeap* FH, Node** root, Node* node); // throw a node to a circular doubly linked list FibonacciHeap* UnionFibonacciHeap(FibonacciHeap* FH1, FibonacciHeap* FH2); // union 2 heaps Node* ExtractMin(FibonacciHeap* FH); // find min and remove min void _RemoveFromRootList(FibonacciHeap* FH, Node* node); // remove a node on root list void _Consolidate(FibonacciHeap* FH); // build binomial heap and set true min void _HeapLink(FibonacciHeap* FH, Node* y, Node* x); // Make y child of x void DecreaseKey(FibonacciHeap* FH, Node* x, int k); // Make a key smaller void _Cut(FibonacciHeap* FH, Node* x, Node* y); // Throw a node from child to root list, reset mark void _CascadingCut(FibonacciHeap* FH, Node* y); // Keep cutting until find a unmarked node Node* Delete(FibonacciHeap* FH, Node* x); // Delete a node int main(void) { FibonacciHeap *FH1 = CreateFibonacciHeap(); FibonacciHeap *FH2 = CreateFibonacciHeap(); FibonacciHeap *FH3 = CreateFibonacciHeap(); Node *N1; Insert(FH1, 1); Insert(FH1, 2); Insert(FH1, 3); Insert(FH2, 4); Insert(FH2, 5); Insert(FH2, 6); FH3 = UnionFibonacciHeap(FH1, FH2); N1 = ExtractMin(FH1); DecreaseKey(FH3, FH3->rootList, 1); Delete(FH3, FH3->rootList); return 0; } // Constructor Node* _CreateNode(int key) { Node *node = (Node*)malloc(sizeof(Node)); node->key = key; node->degree = 0; node->mark = false; node->leftSib = node; node->rightSib = node; node->parent = NULL; node->child = NULL; return node; } // Constructor FibonacciHeap* CreateFibonacciHeap() { FibonacciHeap *FH = (FibonacciHeap*)malloc(sizeof(FibonacciHeap)); FH->n = 0; FH->min = NULL; FH->rootList = NULL; return FH; } // Find the minimum node Node* FindMin(FibonacciHeap* FH) { return FH->min; } // Insert new node Node* Insert(FibonacciHeap* FH, int key) { Node *node = _CreateNode(key); _MergeWithDoublyList(FH, &FH->rootList, node); if ((FH->min == NULL) || (node->key < FH->min->key)) FH->min = node; FH->n++; return node; } // Throw a node to a circular doubly linked list void _MergeWithDoublyList(FibonacciHeap* FH, Node** root, Node* node) { if (*root == NULL) { *root = node; } else { // Insert node in the left next to the root // Adjusting circular doubly linked list for both node and root node->leftSib = *root; node->rightSib = (*root)->rightSib; (*root)->rightSib->leftSib = node; (*root)->rightSib = node; } } // Union 2 heaps FibonacciHeap* UnionFibonacciHeap(FibonacciHeap* FH1, FibonacciHeap* FH2) { FibonacciHeap *FH3 = CreateFibonacciHeap(); // Use FH1's rootList FH3->rootList = FH1->rootList; // Insert FH2 in FH1 root's left FH2->rootList->rightSib->leftSib = FH3->rootList->leftSib; FH3->rootList->leftSib->rightSib = FH2->rootList->rightSib; FH2->rootList->rightSib = FH3->rootList; FH3->rootList->leftSib = FH2->rootList; // Choose the smaller min between FH1 and FH2 if (FH1->min->key < FH2->min->key) { FH3->min = FH1->min; } else { FH3->min = FH2->min; } // Sum up numbers of node FH3->n = FH1->n + FH2->n; return FH3; } // Find min + Remove min // Consolidate the heap Node* ExtractMin(FibonacciHeap* FH) { Node *node = FH->min; Node *temp; Node *next; Node *startPoint; if (node != NULL) { if (node->child != NULL) { // Throw all children to root list temp = node->child; startPoint = node->child; node->child = NULL; node->degree = 0; do { next = temp->rightSib; temp->parent = NULL; temp->rightSib = temp; temp->leftSib = temp; _MergeWithDoublyList(FH, &FH->rootList, temp); // throw it to root list temp = next; } while (temp != startPoint); // while traversed end } // Remove min node _RemoveFromRootList(FH, node); FH->n--; // Do consolidate if (node->rightSib == node) { // node is the only node on root list FH->min = NULL; // (and it disappear now) FH->rootList = NULL; } else { FH->min = node->rightSib; // assign min to its neighbor _Consolidate(FH); // build binomial heap and set ture min } } return node; } // Remove node, noted that min is not corrent void _RemoveFromRootList(FibonacciHeap* FH, Node* node) { // Last node if (node->rightSib == node) { FH->rootList = NULL; FH->min = NULL; } else { // Accidentally delete root if (node == FH->rootList) FH->rootList = node->rightSib; // root right shift // Accidentally delete min if (node == FH->min) FH->min = node->rightSib; // Remove node node->leftSib->rightSib = node->rightSib; node->rightSib->leftSib = node->leftSib; } } // Build binomial heap and set true min void _Consolidate(FibonacciHeap* FH) { Node **A; // the A[] array Node *x, *y; // new tree(iterate), original tree in A[d] Node *temp; // swapping Node *x_copy; Node *next; Node *startingPoint; int num; int i; int d; // degree int size = 0; // size of A // Calculate log2N(size of A) num = FH->n; while (num > 0) { num = num / 2; size++; } // Initialize A A = (Node**)malloc(size * sizeof(Node*)); for (i = 0; i < size; i++) { A[i] = (Node*)malloc(sizeof(Node)); A[i] = NULL; } // x traverse circular list a cycle x = FH->rootList; next = x->rightSib; while (x_copy != next) { x = next; x_copy = x; // copy x for judging loop condition next = x->rightSib; d = x->degree; _RemoveFromRootList(FH, x); // Keep combining and incresing til find a vacant A[d] while (A[d] != NULL) { // A[d] is occupied y = A[d]; // y get the original tree link // Combine trees, // larger root become subtree of smaller root if (x->key > y->key) { temp = x; x = y; y = temp; // exchange x, y } _HeapLink(FH, y, x); // make y child of x A[d] = NULL; d++; // increment degree } A[d] = x; // find a vacant A[d], x landed }; // Add subtrees in A to root list for (i = 0; i < size; i++) { if (A[i] != NULL) { _MergeWithDoublyList(FH, &FH->rootList, A[i]); // throw A[i] to new root list // Find min if ((FH->min == NULL) || (A[i]->key < FH->min->key)) { FH->min = A[i]; } } } } // Make y child of x void _HeapLink(FibonacciHeap* FH, Node* y, Node* x) { y->rightSib = y; y->leftSib = y; _MergeWithDoublyList(FH, &x->child, y); // merge y with x child's doubly list x->degree += 1; y->parent = x; y->mark = false; } void DecreaseKey(FibonacciHeap* FH, Node* x, int k) { Node *y; if (k > x->key) { return; } x->key = k; y = x->parent; if (y != NULL && x->key < y->key) { _Cut(FH, x, y); _CascadingCut(FH, y); } if (x->key < FH->min->key) { FH->min = x; } } // Throw a node from child to root list, reset mark // y is parent, x is child void _Cut(FibonacciHeap* FH, Node* x, Node* y) { // Remove child x from y y->child = NULL; y->degree--; x->parent = NULL; x->rightSib = x; x->leftSib = x; _MergeWithDoublyList(FH, &FH->rootList, x); x->mark = false; } // Keep cutting until find a unmarked node void _CascadingCut(FibonacciHeap* FH, Node* y) { Node *z = y->parent; if (z != NULL) { if (y->mark == false) { y->mark = true; } else { _Cut(FH, y, z); _CascadingCut(FH, z); } } } Node* Delete(FibonacciHeap* FH, Node* x) { DecreaseKey(FH, x, -__INT_MAX__); return ExtractMin(FH); }
Editor is loading...
Leave a Comment