Fibonacci Heap
In this tutorial, you will learn what a Fibonacci Heap is. Also, you will find working examples of different operations on a fibonacci heap in C.
Fibonacci heap is a modified form of a binomial heap with more efficient heap operations than that supported by the binomial and binary heaps.
Unlike binary heap, a node can have more than two children.
The fibonacci heap is called a fibonacci heap because the trees are constructed in a way such that a tree of order n has at least Fn+2 nodes in it, where Fn+2 is the (n + 2)nd Fibonacci number.
Properties of a Fibonacci Heap
Important properties of a Fibonacci heap are:
- It is a set of min heap-ordered trees. (i.e. The parent is always smaller than the children.)
- A pointer is maintained at the minimum element node.
- It consists of a set of marked nodes. (Decrease key operation)
- The trees within a Fibonacci heap are unordered but rooted.
Memory Representation of the Nodes in a Fibonacci Heap
The roots of all the trees are linked together for faster access. The child nodes of a parent node are connected to each other through a circular doubly linked list as shown below.
There are two main advantages of using a circular doubly linked list.
- Deleting a node from the tree takes
O(1)time. - The concatenation of two such lists takes
O(1)time.
Operations on a Fibonacci Heap
Insertion
Algorithm
insert(H, x)
degree[x] = 0
p[x] = NIL
child[x] = NIL
left[x] = x
right[x] = x
mark[x] = FALSE
concatenate the root list containing x with root list H
if min[H] == NIL or key[x] < key[min[H]]
then min[H] = x
n[H] = n[H] + 1
Inserting a node into an already existing heap follows the steps below.
- Create a new node for the element.
- Check if the heap is empty.
- If the heap is empty, set the new node as a root node and mark it min.
- Else, insert the node into the root list and update min.
Find Min
The minimum element is always given by the min pointer.
Union
Union of two fibonacci heaps consists of following steps.
- Concatenate the roots of both the heaps.
- Update min by selecting a minimum key from the new root lists.
Extract Min
It is the most important operation on a fibonacci heap. In this operation, the node with minimum value is removed from the heap and the tree is re-adjusted.
The following steps are followed:
- Delete the min node.
- Set the min-pointer to the next root in the root list.
- Create an array of size equal to the maximum degree of the trees in the heap before deletion.
- Do the following (steps 5-7) until there are no multiple roots with the same degree.
- Map the degree of current root (min-pointer) to the degree in the array.
- Map the degree of next root to the degree in array.
- If there are more than two mappings for the same degree, then apply union operation to those roots such that the min-heap property is maintained (i.e. the minimum is at the root).
An implementation of the above steps can be understood in the example below.
- We will perform an extract-min operation on the heap below.
Fibonacci Heap - Delete the min node, add all its child nodes to the root list and set the min-pointer to the next root in the root list.
Delete the min node - The maximum degree in the tree is 3. Create an array of size 4 and map degree of the next roots with the array.
Create an array - Here, 23 and 7 have the same degrees, so unite them.
Unite those having the same degrees - Again, 7 and 17 have the same degrees, so unite them as well.
Unite those having the same degrees - Again 7 and 24 have the same degree, so unite them.
Unite those having the same degrees - Map the next nodes.
Map the remaining nodes - Again, 52 and 21 have the same degree, so unite them
Unite those having the same degrees - Similarly, unite 21 and 18.
Unite those having the same degrees - Map the remaining root.
Map the remaining nodes - The final heap is.
Final fibonacci heap
Decreasing a Key and Deleting a Node
These are the most important operations which are discussed in Decrease Key and Delete Node Operations.
C Examples
// Operations on a Fibonacci heap in C
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct _NODE {
int key;
int degree;
struct _NODE *left_sibling;
struct _NODE *right_sibling;
struct _NODE *parent;
struct _NODE *child;
bool mark;
bool visited;
} NODE;
typedef struct fibanocci_heap {
int n;
NODE *min;
int phi;
int degree;
} FIB_HEAP;
FIB_HEAP *make_fib_heap();
void insertion(FIB_HEAP *H, NODE *new, int val);
NODE *extract_min(FIB_HEAP *H);
void consolidate(FIB_HEAP *H);
void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x);
NODE *find_min_node(FIB_HEAP *H);
void decrease_key(FIB_HEAP *H, NODE *node, int key);
void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node);
void cascading_cut(FIB_HEAP *H, NODE *parent_node);
void Delete_Node(FIB_HEAP *H, int dec_key);
FIB_HEAP *make_fib_heap(){
FIB_HEAP *H;
H = (FIB_HEAP *)malloc(sizeof(FIB_HEAP));
H->n = 0;
H->min = NULL;
H->phi = 0;
H->degree = 0;
return H;
}
// Printing the heap
void print_heap(NODE *n){
NODE *x;
for (x = n;; x = x->right_sibling) {
if (x->child == NULL) {
printf("node with no child (%d) n", x->key);
} else {
printf("NODE(%d) with child (%d)n", x->key, x->child->key);
print_heap(x->child);
}
if (x->right_sibling == n) {
break;
}
}
}
// Inserting nodes
void insertion(FIB_HEAP *H, NODE *new, int val){
new = (NODE *)malloc(sizeof(NODE));
new->key = val;
new->degree = 0;
new->mark = false;
new->parent = NULL;
new->child = NULL;
new->visited = false;
new->left_sibling = new;
new->right_sibling = new;
if (H->min == NULL) {
H->min = new;
} else {
H->min->left_sibling->right_sibling = new;
new->right_sibling = H->min;
new->left_sibling = H->min->left_sibling;
H->min->left_sibling = new;
if (new->key < H->min->key) {
H->min = new;
}
}
(H->n)++;
}
// Find min node
NODE *find_min_node(FIB_HEAP *H){
if (H == NULL) {
printf(" n Fibonacci heap not yet created n");
return NULL;
} else
return H->min;
}
// Union operation
FIB_HEAP *unionHeap(FIB_HEAP *H1, FIB_HEAP *H2){
FIB_HEAP *Hnew;
Hnew = make_fib_heap();
Hnew->min = H1->min;
NODE *temp1, *temp2;
temp1 = Hnew->min->right_sibling;
temp2 = H2->min->left_sibling;
Hnew->min->right_sibling->left_sibling = H2->min->left_sibling;
Hnew->min->right_sibling = H2->min;
H2->min->left_sibling = Hnew->min;
temp2->right_sibling = temp1;
if ((H1->min == NULL) || (H2->min != NULL && H2->min->key < H1->min->key))
Hnew->min = H2->min;
Hnew->n = H1->n + H2->n;
return Hnew;
}
// Calculate the degree
int cal_degree(int n){
int count = 0;
while (n > 0) {
n = n / 2;
count++;
}
return count;
}
// Consolidate function
void consolidate(FIB_HEAP *H){
int degree, i, d;
degree = cal_degree(H->n);
NODE *A[degree], *x, *y, *z;
for (i = 0; i <= degree; i++) {
A[i] = NULL;
}
x = H->min;
do {
d = x->degree;
while (A[d] != NULL) {
y = A[d];
if (x->key > y->key) {
NODE *exchange_help;
exchange_help = x;
x = y;
y = exchange_help;
}
if (y == H->min)
H->min = x;
fib_heap_link(H, y, x);
if (y->right_sibling == x)
H->min = x;
A[d] = NULL;
d++;
}
A[d] = x;
x = x->right_sibling;
} while (x != H->min);
H->min = NULL;
for (i = 0; i < degree; i++) {
if (A[i] != NULL) {
A[i]->left_sibling = A[i];
A[i]->right_sibling = A[i];
if (H->min == NULL) {
H->min = A[i];
} else {
H->min->left_sibling->right_sibling = A[i];
A[i]->right_sibling = H->min;
A[i]->left_sibling = H->min->left_sibling;
H->min->left_sibling = A[i];
if (A[i]->key < H->min->key) {
H->min = A[i];
}
}
if (H->min == NULL) {
H->min = A[i];
} else if (A[i]->key < H->min->key) {
H->min = A[i];
}
}
}
}
// Linking
void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x){
y->right_sibling->left_sibling = y->left_sibling;
y->left_sibling->right_sibling = y->right_sibling;
if (x->right_sibling == x)
H->min = x;
y->left_sibling = y;
y->right_sibling = y;
y->parent = x;
if (x->child == NULL) {
x->child = y;
}
y->right_sibling = x->child;
y->left_sibling = x->child->left_sibling;
x->child->left_sibling->right_sibling = y;
x->child->left_sibling = y;
if ((y->key) < (x->child->key))
x->child = y;
(x->degree)++;
}
// Extract min
NODE *extract_min(FIB_HEAP *H){
if (H->min == NULL)
printf("n The heap is empty");
else {
NODE *temp = H->min;
NODE *pntr;
pntr = temp;
NODE *x = NULL;
if (temp->child != NULL) {
x = temp->child;
do {
pntr = x->right_sibling;
(H->min->left_sibling)->right_sibling = x;
x->right_sibling = H->min;
x->left_sibling = H->min->left_sibling;
H->min->left_sibling = x;
if (x->key < H->min->key)
H->min = x;
x->parent = NULL;
x = pntr;
} while (pntr != temp->child);
}
(temp->left_sibling)->right_sibling = temp->right_sibling;
(temp->right_sibling)->left_sibling = temp->left_sibling;
H->min = temp->right_sibling;
if (temp == temp->right_sibling && temp->child == NULL)
H->min = NULL;
else {
H->min = temp->right_sibling;
consolidate(H);
}
H->n = H->n - 1;
return temp;
}
return H->min;
}
void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node){
NODE *temp_parent_check;
if (node_to_be_decrease == node_to_be_decrease->right_sibling)
parent_node->child = NULL;
node_to_be_decrease->left_sibling->right_sibling = node_to_be_decrease->right_sibling;
node_to_be_decrease->right_sibling->left_sibling = node_to_be_decrease->left_sibling;
if (node_to_be_decrease == parent_node->child)
parent_node->child = node_to_be_decrease->right_sibling;
(parent_node->degree)--;
node_to_be_decrease->left_sibling = node_to_be_decrease;
node_to_be_decrease->right_sibling = node_to_be_decrease;
H->min->left_sibling->right_sibling = node_to_be_decrease;
node_to_be_decrease->right_sibling = H->min;
node_to_be_decrease->left_sibling = H->min->left_sibling;
H->min->left_sibling = node_to_be_decrease;
node_to_be_decrease->parent = NULL;
node_to_be_decrease->mark = false;
}
void cascading_cut(FIB_HEAP *H, NODE *parent_node){
NODE *aux;
aux = parent_node->parent;
if (aux != NULL) {
if (parent_node->mark == false) {
parent_node->mark = true;
} else {
cut(H, parent_node, aux);
cascading_cut(H, aux);
}
}
}
void decrease_key(FIB_HEAP *H, NODE *node_to_be_decrease, int new_key){
NODE *parent_node;
if (H == NULL) {
printf("n FIbonacci heap not created ");
return;
}
if (node_to_be_decrease == NULL) {
printf("Node is not in the heap");
}
else {
if (node_to_be_decrease->key < new_key) {
printf("n Invalid new key for decrease key operation n ");
} else {
node_to_be_decrease->key = new_key;
parent_node = node_to_be_decrease->parent;
if ((parent_node != NULL) && (node_to_be_decrease->key < parent_node->key)) {
printf("n cut called");
cut(H, node_to_be_decrease, parent_node);
printf("n cascading cut called");
cascading_cut(H, parent_node);
}
if (node_to_be_decrease->key < H->min->key) {
H->min = node_to_be_decrease;
}
}
}
}
void *find_node(FIB_HEAP *H, NODE *n, int key, int new_key){
NODE *find_use = n;
NODE *f = NULL;
find_use->visited = true;
if (find_use->key == key) {
find_use->visited = false;
f = find_use;
decrease_key(H, f, new_key);
}
if (find_use->child != NULL) {
find_node(H, find_use->child, key, new_key);
}
if ((find_use->right_sibling->visited != true)) {
find_node(H, find_use->right_sibling, key, new_key);
}
find_use->visited = false;
}
FIB_HEAP *insertion_procedure(){
FIB_HEAP *temp;
int no_of_nodes, ele, i;
NODE *new_node;
temp = (FIB_HEAP *)malloc(sizeof(FIB_HEAP));
temp = NULL;
if (temp == NULL) {
temp = make_fib_heap();
}
printf(" n enter number of nodes to be insert = ");
scanf("%d", &no_of_nodes);
for (i = 1; i <= no_of_nodes; i++) {
printf("n node %d and its key value = ", i);
scanf("%d", &ele);
insertion(temp, new_node, ele);
}
return temp;
}
void Delete_Node(FIB_HEAP *H, int dec_key){
NODE *p = NULL;
find_node(H, H->min, dec_key, -5000);
p = extract_min(H);
if (p != NULL)
printf("n Node deleted");
else
printf("n Node not deleted:some error");
}
int main(int argc, char **argv){
NODE *new_node, *min_node, *extracted_min, *node_to_be_decrease, *find_use;
FIB_HEAP *heap, *h1, *h2;
int operation_no, new_key, dec_key, ele, i, no_of_nodes;
heap = (FIB_HEAP *)malloc(sizeof(FIB_HEAP));
heap = NULL;
while (1) {
printf(" n Operations n 1. Create Fibonacci heap n 2. Insert nodes into fibonacci heap n 3. Find min n 4. Union n 5. Extract min n 6. Decrease key n 7.Delete node n 8. print heap n 9. exit n enter operation_no = ");
scanf("%d", &operation_no);
switch (operation_no) {
case 1:
heap = make_fib_heap();
break;
case 2:
if (heap == NULL) {
heap = make_fib_heap();
}
printf(" enter number of nodes to be insert = ");
scanf("%d", &no_of_nodes);
for (i = 1; i <= no_of_nodes; i++) {
printf("n node %d and its key value = ", i);
scanf("%d", &ele);
insertion(heap, new_node, ele);
}
break;
case 3:
min_node = find_min_node(heap);
if (min_node == NULL)
printf("No minimum value");
else
printf("n min value = %d", min_node->key);
break;
case 4:
if (heap == NULL) {
printf("n no FIbonacci heap created n ");
break;
}
h1 = insertion_procedure();
heap = unionHeap(heap, h1);
printf("Unified Heap:n");
print_heap(heap->min);
break;
case 5:
if (heap == NULL)
printf("Empty Fibonacci heap");
else {
extracted_min = extract_min(heap);
printf("n min value = %d", extracted_min->key);
printf("n Updated heap: n");
print_heap(heap->min);
}
break;
case 6:
if (heap == NULL)
printf("Fibonacci heap is empty");
else {
printf(" n node to be decreased = ");
scanf("%d", &dec_key);
printf(" n enter the new key = ");
scanf("%d", &new_key);
find_use = heap->min;
find_node(heap, find_use, dec_key, new_key);
printf("n Key decreased- Corresponding heap:n");
print_heap(heap->min);
}
break;
case 7:
if (heap == NULL)
printf("Fibonacci heap is empty");
else {
printf(" n Enter node key to be deleted = ");
scanf("%d", &dec_key);
Delete_Node(heap, dec_key);
printf("n Node Deleted- Corresponding heap:n");
print_heap(heap->min);
break;
}
case 8:
print_heap(heap->min);
break;
case 9:
free(new_node);
free(heap);
exit(0);
default:
printf("Invalid choice ");
}
}
}Complexities
| Insertion | O(1) |
| Find Min | O(1) |
| Union | O(1) |
| Extract Min | O(log n) |
| Decrease Key | O(1) |
| Delete Node | O(log n) |
Fibonacci Heap Applications
- To improve the asymptotic running time of Dijkstra’s algorithm.
Python Example for Beginners
Two Machine Learning Fields
There are two sides to machine learning:
- Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
- Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.
Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes
Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!
Latest end-to-end Learn by Coding Recipes in Project-Based Learning:
Applied Statistics with R for Beginners and Business Professionals
Data Science and Machine Learning Projects in Python: Tabular Data Analytics
Data Science and Machine Learning Projects in R: Tabular Data Analytics
Python Machine Learning & Data Science Recipes: Learn by Coding
R Machine Learning & Data Science Recipes: Learn by Coding
Comparing Different Machine Learning Algorithms in Python for Classification (FREE)
Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.