5. FIBONACCI HEAP IMPLEMENTATION
AIM:
To write a java program
for Fibonacci heap implement.
ALGORITHM:
1. Call
the buildMinHeap() function on the list. 2. insert(x) inserts a node x into the heap.
3. minimum() returns the node in the heap with minimum key.
4. extractMin() deletes the node with minimum key from the heap.
5. union(H) merge heap H and create a new one.
6. decreaseKey(x,k) assigns to node x within the heap the new key value k, which is assumed to be no greater than its current key value.
7. delete(x) deletes node x from the heap.
PROGRAM :
importjava.util.*;
classFibonacciHeapNode
{
FibonacciHeapNode child, left, right, parent;
int element;
publicFibonacciHeapNode(int element)
{
this.right = this;
this.left = this;
this.element = element;
}
}
classFibonacciHeap
{
privateFibonacciHeapNode root;
privateint count;
publicFibonacciHeap()
{
root = null;
count = 0;
}
publicbooleanisEmpty()
{
return root == null;
}
public void clear()
{
root = null;
count = 0;
}
public void insert(int element)
{
FibonacciHeapNode node = new FibonacciHeapNode(element);
node.element = element;
if (root != null)
{
node.left = root;
node.right = root.right;
root.right = node;
node.right.left = node;
if (element <root.element)
root = node;
}
else
root = node;
count++;
}
public void display()
{
System.out.print("\nHeap = ");
FibonacciHeapNodeptr = root;
if (ptr == null)
{
System.out.print("Empty\n");
return;
}
do
{
System.out.print(ptr.element +" ");
ptr = ptr.right;
} while (ptr != root &&ptr.right != null);
System.out.println();
}
}
public class FibonacciHeapTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("FibonacciHeap Test\n\n");
FibonacciHeapfh = new FibonacciHeap();
charch;
do
{
System.out.println("\nFibonacciHeap
Operations\n");
System.out.println("1. insert element ");
System.out.println("2. check empty");
System.out.println("3. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter element");
fh.insert(scan.nextInt() );
break;
case 2 :
System.out.println("Empty status = "+
fh.isEmpty());
break;
case 3 :
fh.clear();
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
fh.display();
System.out.println("\nDo you want to continue (Type y
or n)\n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}