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

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3