Operations on fibonacci heaps

Algorithm for insertion
Input	Fibonacci heap.
Output	Fibonacci heap after insertion
Complexity	O(l).

FIB-HEAP-INSERT(H, x)
1    degree[x] = 0
2    p[x] =NIL
3    child[x] = NIL
4    left[x] =x
5    right[x] = x
6    mark[x] = FALSE
7    concatenate the root list containing x with root list H
8    if min[H] = NIL or key[x] < key[min[H]]
9    then min[H] =x
10   n[H] =n[H] + 1

Algorithm for union
Input	Two Fibonacci heap H1 and H2.
Output	Fibonacci heap after union
Complexity	O(l).

FIB-HEAP-UNION (H1, H2)
1   H = MAKE-FIB-HEAP()
2   min[H] = min[H1]
3   concatenate the root list of H2 with the root list of H
4   if (min[H1] = NIL) or (min[H2] ≠ NIL and min[H2] < min[H1])
5   then min[H] = min[H2]
6   n[H] =n[H1] + n[H2]
7   free the objects H1 and H2
8   return H

Extracting the minimum node
Input	Fibonacci heap H.
Output	Pointer of Fibonacci heap which point min. 
Complexity	O(lgN).

FIB-HEAP-EXTRACT-MIN(H)
1 z = min[H]
2 if z ≠ NIL
3 then for each child x of z
4 do add x to the root list of H
5 p[x] = NIL
6 remove z from the root list of H
7 if z = right[z]
8 then min[H] = NIL
9 else min[H] = right[z]
10 CONSOLIDATE(H)
11 n[H] =n[H] - 1
12 return z

CONSOLIDATE (H)
1   for i =0 to D (n[H])
2   do A[i] = NIL
3   for each node w in the root list of H
4   do x = w
5   d =degree[x]
6   while A[d] ≠ NIL
7   do y =A[d]   // Another node with the same degree as x.
8   if key[x] > key[y]
9   then exchange x ↔ y
10   FIB-HEAP-LINK(H, y, x)
11   A[d] = NIL
12    d =d + 1
13   A[d] =x
14     min[H] = NIL
15    for i =0 to D(n[H])
16     do if A[i] ≠ NIL
17    then add A[i] to the root list of H
18   if min[H] = NIL or key[A[i]] < key[min[H]]
19   then min[H] = A[i]
FIB-HEAP-LINK(H, y, x)
1   remove y from the root list of H
2   make y a child of x, incrementing degree[x]
3   mark[y] =FALSE

Decreasing a key
Input	 Fibonacci heap H .
Output	Fibonacci heap after decrease  key
Complexity	O(l).

FIB-HEAP-DECREASE-KEY(H, x, k)
1 if k > key[x]
2 then error "new key is greater than current key"
3 key[x] =k
4 y =p[x]
5 if y ≠ NIL and key[x] < key[y]
6 then CUT(H, x, y)
7 CASCADING-CUT(H, y)
8 if key[x] < key[min[H]]
9 then min[H] =x
CUT(H, x, y)
1 remove x from the child list of y, decrementing degree[y]
2 add x to the root list of H
3 p[x] = NIL
4 mark[x] = FALSE
CASCADING-CUT(H, y)
1 z =p[y]
2 if z ≠ NIL
3 then if mark[y] = FALSE
4 then mark[y] = TRUE
5 else CUT(H, y, z)
6 CASCADING-CUT(H, z)

Deleting a node
Input	Fibonacci heap H.
Output	Fibonacci heap after deleting node . 
Complexity	O(lgN).

FIB-HEAP-DELETE(H, x)
  1 FIB-HEAP-DECREASE-KEY(H, x, -∞)
  2 FIB-HEAP-EXTRACT-MIN(H)

// Fibonacci heap

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<malloc.h>

# define NIL 0

int nNodes;
// structure of a node

struct fheap_node
{
	struct fheap_node *parent;
	struct fheap_node *left;
	struct fheap_node *right;
	struct fheap_node *child;
	int degree;
	int mark;               // boolean
	int key;
};
struct fheap_node *min,*min1;

// create fibonacci heap

 create_fib()
{
	min->parent=NIL;
	min->key=NIL;
	min->left=NIL;
	min->right=NIL;
	min->child=NIL;
	nNodes=0;

}

//Insert in fibonacci heap

Finsert(int val)
{
	struct fheap_node *fheap;
	fheap=malloc(sizeof(struct fheap_node));
	fheap->key=val;
	fheap->parent=NIL;
	fheap->left=NIL;
	fheap->right=NIL;
	fheap->child=NIL;
	if(min->key!=NIL)
	{
		fheap->right=min;
		fheap->left=min->left;
		(min)->left=fheap;
		(fheap->left)->right=fheap;
		if(val<min->key)
			min=fheap;
	 }
	else
		{
		min=fheap;
		min->left=min;
		min->right=min;
		}

       nNodes++;
}

//Display heap

void display(struct node *min1)
{
	struct fheap_node *q,*chil;
	if(min==NIL)
	{
		printf("fib heap is empty");
		return;
	}
	q=min;
	printf("Fib heap display");
	do
	{
		printf("\t %d ",q->key);
		if(q->child!=NIL)
		{
		      display(q->child);
		}
		q=q->right;
	}while(q!=min);
}

// find minimum in heap

void findmin()
{
	printf("\nminimum is %d: ",min->key);
}

int main()
{
	int option,n,i,m;
	clrscr();
	min=NIL;
	while(1)
	{
		printf("menu\n");
		printf("1: create fibonacci heap \n");
		printf("2: insert in fibonacci heap \n");
		printf("3: Find min in fibonacci heap \n");
		printf("4: display ");
		printf("5: exit ");
		scanf("%d",&option);
		switch(option)
		{
			case 1:create_fib();
				break;
			case 2: printf("enter the element");
			scanf("%d",&n);
			Finsert(n);
				break;
			case 3:findmin();
				break;
			case 4: display(min1);
				break;
			case 5: exit(1);
			default: printf("wrong choice");
		}
	}
}