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:
Collect a Java Stream to an Immutable Collection
Jackson Ignore Properties on Marshalling
Logout in an OAuth Secured Application
Java Program to Implement Branch and Bound Method to Perform a Combinatorial Search
Dynamic Proxies in Java
Remove HTML tags from a file to extract only the TEXT
Convert Character Array to String in Java
Java Program to Check Multiplicability of Two Matrices
New Features in Java 10
Introduction to Netflix Archaius with Spring Cloud
Quick Intro to Spring Cloud Configuration
Spring Security 5 for Reactive Applications
Practical Java Examples of the Big O Notation
Spring Cloud AWS – RDS
Java Timer
Chương trình Java đầu tiên
Spring Boot - Apache Kafka
Map to String Conversion in Java
Hướng dẫn Java Design Pattern – Prototype
Java Program to Perform Searching Based on Locality of Reference
Guide to the Volatile Keyword in Java
Logout in an OAuth Secured Application
Using a Mutex Object in Java
Java Program to Implement Heap’s Algorithm for Permutation of N Numbers
Spring Cloud – Adding Angular
Java Program to Implement Binary Heap
Java Program to Implement Hash Tree
Spring REST API with Protocol Buffers
Java Program to Implement Fermat Primality Test Algorithm
Java Program to Implement Best-First Search
HashSet trong java
A Guide to @RepeatedTest in Junit 5