This is a Java Program to implement Binomial Heap. A binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation. This program is based on the implementation by Willem Visser .
Here is the source code of the Java program to implement Binomial Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/* * Java Program to Implement Binomial Heap */ import java.util.Scanner; /* Class BinomialHeapNode */ class BinomialHeapNode { int key, degree; BinomialHeapNode parent; BinomialHeapNode sibling; BinomialHeapNode child; /* Constructor */ public BinomialHeapNode(int k) { key = k; degree = 0; parent = null; sibling = null; child = null; } /* Function reverse */ public BinomialHeapNode reverse(BinomialHeapNode sibl) { BinomialHeapNode ret; if (sibling != null) ret = sibling.reverse(this); else ret = this; sibling = sibl; return ret; } /* Function to find min node */ public BinomialHeapNode findMinNode() { BinomialHeapNode x = this, y = this; int min = x.key; while (x != null) { if (x.key < min) { y = x; min = x.key; } x = x.sibling; } return y; } /* Function to find node with key value */ public BinomialHeapNode findANodeWithKey(int value) { BinomialHeapNode temp = this, node = null; while (temp != null) { if (temp.key == value) { node = temp; break; } if (temp.child == null) temp = temp.sibling; else { node = temp.child.findANodeWithKey(value); if (node == null) temp = temp.sibling; else break; } } return node; } /* Function to get size */ public int getSize() { return (1 + ((child == null) ? 0 : child.getSize()) + ((sibling == null) ? 0 : sibling.getSize())); } } /* class BinomialHeap */ class BinomialHeap { private BinomialHeapNode Nodes; private int size; /* Constructor */ public BinomialHeap() { Nodes = null; size = 0; } /* Check if heap is empty */ public boolean isEmpty() { return Nodes == null; } /* Function to get size */ public int getSize() { return size; } /* clear heap */ public void makeEmpty() { Nodes = null; size = 0; } /* Function to insert */ public void insert(int value) { if (value > 0) { BinomialHeapNode temp = new BinomialHeapNode(value); if (Nodes == null) { Nodes = temp; size = 1; } else { unionNodes(temp); size++; } } } /* Function to unite two binomial heaps */ private void merge(BinomialHeapNode binHeap) { BinomialHeapNode temp1 = Nodes, temp2 = binHeap; while ((temp1 != null) && (temp2 != null)) { if (temp1.degree == temp2.degree) { BinomialHeapNode tmp = temp2; temp2 = temp2.sibling; tmp.sibling = temp1.sibling; temp1.sibling = tmp; temp1 = tmp.sibling; } else { if (temp1.degree < temp2.degree) { if ((temp1.sibling == null) || (temp1.sibling.degree > temp2.degree)) { BinomialHeapNode tmp = temp2; temp2 = temp2.sibling; tmp.sibling = temp1.sibling; temp1.sibling = tmp; temp1 = tmp.sibling; } else { temp1 = temp1.sibling; } } else { BinomialHeapNode tmp = temp1; temp1 = temp2; temp2 = temp2.sibling; temp1.sibling = tmp; if (tmp == Nodes) { Nodes = temp1; } else { } } } } if (temp1 == null) { temp1 = Nodes; while (temp1.sibling != null) { temp1 = temp1.sibling; } temp1.sibling = temp2; } else { } } /* Function for union of nodes */ private void unionNodes(BinomialHeapNode binHeap) { merge(binHeap); BinomialHeapNode prevTemp = null, temp = Nodes, nextTemp = Nodes.sibling; while (nextTemp != null) { if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null) && (nextTemp.sibling.degree == temp.degree))) { prevTemp = temp; temp = nextTemp; } else { if (temp.key <= nextTemp.key) { temp.sibling = nextTemp.sibling; nextTemp.parent = temp; nextTemp.sibling = temp.child; temp.child = nextTemp; temp.degree++; } else { if (prevTemp == null) { Nodes = nextTemp; } else { prevTemp.sibling = nextTemp; } temp.parent = nextTemp; temp.sibling = nextTemp.child; nextTemp.child = temp; nextTemp.degree++; temp = nextTemp; } } nextTemp = temp.sibling; } } /* Function to return minimum key */ public int findMinimum() { return Nodes.findMinNode().key; } /* Function to delete a particular element */ public void delete(int value) { if ((Nodes != null) && (Nodes.findANodeWithKey(value) != null)) { decreaseKeyValue(value, findMinimum() - 1); extractMin(); } } /* Function to decrease key with a given value */ public void decreaseKeyValue(int old_value, int new_value) { BinomialHeapNode temp = Nodes.findANodeWithKey(old_value); if (temp == null) return; temp.key = new_value; BinomialHeapNode tempParent = temp.parent; while ((tempParent != null) && (temp.key < tempParent.key)) { int z = temp.key; temp.key = tempParent.key; tempParent.key = z; temp = tempParent; tempParent = tempParent.parent; } } /* Function to extract the node with the minimum key */ public int extractMin() { if (Nodes == null) return -1; BinomialHeapNode temp = Nodes, prevTemp = null; BinomialHeapNode minNode = Nodes.findMinNode(); while (temp.key != minNode.key) { prevTemp = temp; temp = temp.sibling; } if (prevTemp == null) { Nodes = temp.sibling; } else { prevTemp.sibling = temp.sibling; } temp = temp.child; BinomialHeapNode fakeNode = temp; while (temp != null) { temp.parent = null; temp = temp.sibling; } if ((Nodes == null) && (fakeNode == null)) { size = 0; } else { if ((Nodes == null) && (fakeNode != null)) { Nodes = fakeNode.reverse(null); size = Nodes.getSize(); } else { if ((Nodes != null) && (fakeNode == null)) { size = Nodes.getSize(); } else { unionNodes(fakeNode.reverse(null)); size = Nodes.getSize(); } } } return minNode.key; } /* Function to display heap */ public void displayHeap() { System.out.print("\nHeap : "); displayHeap(Nodes); System.out.println("\n"); } private void displayHeap(BinomialHeapNode r) { if (r != null) { displayHeap(r.child); System.out.print(r.key +" "); displayHeap(r.sibling); } } } /* Class BinomialHeapTest */ public class BinomialHeapTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Binomial Heap Test\n\n"); /* Make object of BinomialHeap */ BinomialHeap bh = new BinomialHeap( ); char ch; /* Perform BinomialHeap operations */ do { System.out.println("\nBinomialHeap Operations\n"); System.out.println("1. insert "); System.out.println("2. delete "); System.out.println("3. size"); System.out.println("4. check empty"); System.out.println("5. clear"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer element to insert"); bh.insert( scan.nextInt() ); break; case 2 : System.out.println("Enter element to delete "); bh.delete( scan.nextInt() ); break; case 3 : System.out.println("Size = "+ bh.getSize()); break; case 4 : System.out.println("Empty status = "+ bh.isEmpty()); break; case 5 : bh.makeEmpty(); System.out.println("Heap Cleared\n"); break; default : System.out.println("Wrong Entry \n "); break; } /* Display heap */ bh.displayHeap(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
Binomial Heap Test BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 1 Enter integer element to insert 73 Heap : 73 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 1 Enter integer element to insert 19 Heap : 73 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 1 Enter integer element to insert 24 Heap : 24 73 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 1 Enter integer element to insert 51 Heap : 51 24 73 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 1 Enter integer element to insert 99 Heap : 99 51 24 73 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 3 Size = 5 Heap : 99 51 24 73 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 2 Enter element to delete 51 Heap : 99 73 24 19 Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 5 Heap Cleared Heap : Do you want to continue (Type y or n) y BinomialHeap Operations 1. insert 2. delete 3. size 4. check empty 5. clear 4 Empty status = true Heap : Do you want to continue (Type y or n) n
Related posts:
Java Program to Find the Connected Components of an UnDirected Graph
Java Program to Implement Gauss Jordan Elimination
Guide to CopyOnWriteArrayList
Loại bỏ các phần tử trùng trong một ArrayList như thế nào?
Java Program to Perform Addition Operation Using Bitwise Operators
Toán tử trong java
Versioning a REST API
Java Program to Implement Meldable Heap
Comparing Arrays in Java
Hướng dẫn sử dụng String Format trong Java
Spring Boot - Cloud Configuration Client
Guide to Java OutputStream
Java Program to Implement Sorted Singly Linked List
Java Program to Implement Extended Euclid Algorithm
Object cloning trong java
Hashtable trong java
Spring Cloud – Adding Angular
Disable DNS caching
Partition a List in Java
Guava Collections Cookbook
Practical Java Examples of the Big O Notation
Java Program to Implement Park-Miller Random Number Generation Algorithm
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Spring Cloud Bus
Java Program to Implement Double Order Traversal of a Binary Tree
How to Manually Authenticate User with Spring Security
Java Program to implement Priority Queue
Dockerizing a Spring Boot Application
Hướng dẫn Java Design Pattern – Proxy
Java 8 – Powerful Comparison with Lambdas
Java Program to implement Bi Directional Map
Write/Read cookies using HTTP and Read a file from the internet