This is a Java Program to Implement Meldable Heap. A randomized meldable heap (also Meldable Heap or Randomized Meldable Priority Queue) is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree. However, there are no restrictions on the shape of the underlying binary tree.
Here is the source code of the Java Program to Implement Meldable Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** ** Java Program to Implement Meldable Heap **/ import java.util.Scanner; import java.util.Random; /** Class Node **/ class Node { Node left, right, parent; int x; public Node(Node parent, Node left, Node right, int x) { this.parent = parent; this.left = left; this.right = right; this.x = x; } } /** Class MedlableHeap **/ class MeldableHeap { private Random rand; private int n; private Node root; public MeldableHeap() { root = null; rand = new Random(); n = 0; } /** Check if heap is empty **/ public boolean isEmpty() { return root == null; } /** clear heap **/ public void makeEmpty() { root = null; rand = new Random(); n = 0; } /** function to get size **/ public int getSize() { return n; } /** function to insert an element **/ public void add(int x) { Node u = new Node(null, null, null, x); root = meld(u, root); root.parent = null; n++; } /** function to remove an element **/ public int remove() { int x = root.x; root = meld(root.left, root.right); if (root != null) root.parent = null; n--; return x; } /** function to merge two nodes **/ public Node meld(Node q1, Node q2) { if (q1 == null) return q2; if (q2 == null) return q1; if (q2.x < q1.x) return meld(q2, q1); if (rand.nextBoolean()) { q1.left = meld(q1.left, q2); q1.left.parent = q1; } else { q1.right = meld(q1.right, q2); q1.right.parent = q1; } return q1; } /** function to print heap **/ public void displayHeap() { System.out.print("\nMeldable Heap : "); if (root == null) { System.out.print("Empty\n"); return; } Node prev, w = root; while (w.left != null) w = w.left; while (w != null) { System.out.print(w.x +" "); prev = w; w = nextNode(w); } System.out.println(); } /** function to get next node in heap **/ private Node nextNode(Node w) { if (w.right != null) { w = w.right; while (w.left != null) w = w.left; } else { while (w.parent != null && w.parent.left != w) w = w.parent; w = w.parent; } return w; } } /** Class MeldableHeapTest **/ public class MeldableHeapTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("Meldable Heap Test\n\n"); /* Make object of MeldableHeap */ MeldableHeap mh = new MeldableHeap(); char ch; /* Perform Meldable Heap operations */ do { System.out.println("\nMeldable Heap Operations\n"); System.out.println("1. add"); System.out.println("2. remove"); 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"); mh.add( scan.nextInt() ); break; case 2 : System.out.println("Removed Element : "+ mh.remove() ); break; case 3 : System.out.println("Size = "+ mh.getSize()); break; case 4 : System.out.println("Empty status = "+ mh.isEmpty()); break; case 5 : mh.makeEmpty(); System.out.println("Heap Cleared\n"); break; default : System.out.println("Wrong Entry \n "); break; } /* Display heap */ mh.displayHeap(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
Meldable Heap Test Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 4 Empty status = true Meldable Heap : Empty Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 24 Meldable Heap : 24 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 6 Meldable Heap : 24 6 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 28 Meldable Heap : 28 24 6 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 94 Meldable Heap : 28 24 6 94 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 19 Meldable Heap : 28 24 6 19 94 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 5 Meldable Heap : 28 24 6 19 94 5 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 1 Enter integer element to insert 63 Meldable Heap : 28 24 6 19 94 5 63 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 3 Size = 7 Meldable Heap : 28 24 6 19 94 5 63 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 2 Removed Element : 5 Meldable Heap : 28 63 24 6 19 94 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 2 Removed Element : 6 Meldable Heap : 28 63 24 19 94 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 2 Removed Element : 19 Meldable Heap : 28 63 24 94 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 2 Removed Element : 24 Meldable Heap : 94 28 63 Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 5 Heap Cleared Meldable Heap : Empty Do you want to continue (Type y or n) y Meldable Heap Operations 1. add 2. remove 3. size 4. check empty 5. clear 4 Empty status = true Meldable Heap : Empty Do you want to continue (Type y or n) n
Related posts:
A Guide To UDP In Java
Logging a Reactive Sequence
Java 8 Predicate Chain
Java Program to Implement Find all Forward Edges in a Graph
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Guide to the Fork/Join Framework in Java
Spring WebClient vs. RestTemplate
Converting Between a List and a Set in Java
Java Program to Implement Interpolation Search Algorithm
Hướng dẫn sử dụng Java Reflection
A Guide to Java HashMap
Batch Processing with Spring Cloud Data Flow
Java String to InputStream
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Implement Sorted Vector
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Java Program to Construct an Expression Tree for an Postfix Expression
Spring Boot - Build Systems
Compare Two JSON Objects with Jackson
Java Program to Implement Max Heap
REST Web service: Basic Authentication trong Jersey 2.x
Java Scanner hasNext() vs. hasNextLine()
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Quick Guide to the Java StringTokenizer
The XOR Operator in Java
Java Web Services – JAX-WS – SOAP
New Stream Collectors in Java 9
Hướng dẫn Java Design Pattern – Visitor
Java Program to Convert a Decimal Number to Binary Number using Stacks
Cài đặt và sử dụng Swagger UI
Spring Boot Actuator
Spring AMQP in Reactive Applications