Java Program To Implement Fibonacci Heap
Chapter:
Data Structures
Last Updated:
12-07-2016 18:44:27 UTC
Program:
/* ............... START ............... */
import java.util.*;
class FibonacciHeapNode {
FibonacciHeapNode child, left, right, parent;
int element;
public FibonacciHeapNode(int element) {
this.right = this;
this.left = this;
this.element = element;
}
}
class FibonacciHeap {
private FibonacciHeapNode root;
private int count;
public FibonacciHeap() {
root = null;
count = 0;
}
public boolean isEmpty() {
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 = ");
FibonacciHeapNode ptr = 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 JavaFibonacciHeapExample {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("FibonacciHeap Test\n\n");
FibonacciHeap fh = new FibonacciHeap();
char ch;
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');
}
}
/* ............... END ............... */
Output
FibonacciHeap Test
FibonacciHeap Operations
1. insert element
2. check empty
3. clear
1
Enter element
2
Heap = 2
Do you want to continue (Type y or n)
y
FibonacciHeap Operations
1. insert element
2. check empty
3. clear
2
Empty status = false
Heap = 2
Do you want to continue (Type y or n)
y
FibonacciHeap Operations
1. insert element
2. check empty
3. clear
2
Empty status = false
Heap = 2
Do you want to continue (Type y or n)
Tags
Implement Fibonacci Heap, Java, Data Structure