Fibonacci Heap – Insertion and Union

Last Updated on June 29, 2022 by Ria Pathak

Fibonacci Heap:

Fibonacci heap is a data structure which collectionis a collection of trees having max heap or min-heap properties. These two properties are the characteristics of the fibonacci heap tree. In Fibonacci heaps, trees can be of any shape even if all the trees can have a single node.

In this, Node may have more than two childrens or no childrens at all.

Fibonacci heap has efficient operations as compared to binary and binomial heap.

As, in the name clearly mentioned, fibonacci means the fibonacci heap is constructed in such a way that the tree with order n has Fn+2 nodes where Fn+2 is the fibonacci number.

Properties of Fibonacci Heap:

• Fibonacci heap is a set of min heap ordered trees.
• The pointer is placed at the minimum value node.
• A Fibonacci heap is a set of marked nodes i.e. Decrease key operation.

In the Fibonacci heap, the roots of all the trees are linked together for better and faster access.

Operations of the Fibonacci heap:

1. Insertion: To insert a node in the Fibonacci heap, we will follow the following algorithm.

Algorithm:

• Create a new node ‘d’.

• Check if the existing heap is empty or not.

• If the heap is empty:

• Make ‘d’ the only node in the heap.

• Set a min pointer to the ‘d’.

• Else insert ‘d’ into the heap and update the heap.

2. Union: Union of two Fibonacci heaps is done as follows:

Let’s consider two Fibonacci heaps h1 and h2.

Algorithm:

• Join the root node of both the heaps i.e. h1 and h2 and make a single Fibonacci heap (h3).
• If min of h1 < min of h2 then, the min of h3 is equal to the min of h1.
• Else mark the min of h3 is equal to the min of h2.

Code Implementation

#include <cstdlib>
#include <iostream>
#include <malloc.h>
using namespace std;

struct node {
	node* parent;
	node* child;
	node* left;
	node* right;
	int key;
};

struct node* mini = NULL;

int no_of_nodes = 0;

void insertion(int val)
{
	struct node* new_node = (struct node*)malloc(sizeof(struct node));
	new_node->key = val;
	new_node->parent = NULL;
	new_node->child = NULL;
	new_node->left = new_node;
	new_node->right = new_node;
	if (mini != NULL) {
		(mini->left)->right = new_node;
		new_node->right = mini;
		new_node->left = mini->left;
		mini->left = new_node;
		if (new_node->key < mini->key)
			mini = new_node;
	}
	else {
		mini = new_node;
	}
}

void display(struct node* mini)
{
	node* ptr = mini;
	if (ptr == NULL)
		cout << "The Heap is Empty" << endl;

	else {
		cout << "The root nodes of Heap are: " << endl;
		do {
			cout << ptr->key;
			ptr = ptr->right;
			if (ptr != mini) {
				cout << "-->";
			}
		} while (ptr != mini && ptr->right != NULL);
		cout << endl
			<< "The heap has " << no_of_nodes << " nodes" << endl;
	}
}
void find_min(struct node* mini)
{
	cout << "min of heap is: " << mini->key << endl;
}


int main()
{

	no_of_nodes = 7;
	insertion(4);
	insertion(3);
	insertion(7);
	insertion(5);
	insertion(2);
	insertion(1);
	insertion(10);

	display(mini);

	find_min(mini);

	return 0;
}

Complexity:

Insertion : O(1)
Union: O(1)

This article tried to discuss Fibonacci Heap – Insertion and Union. Hope this blog helps you understand the concept. To practice problems feel free to check MYCODE | Competitive Programming at Prepbytes.