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:
Iterating over Enum Values in Java
Spring Security OAuth Login with WebFlux
XML-Based Injection in Spring
Phương thức forEach() trong java 8
Custom JUnit 4 Test Runners
Hướng dẫn Java Design Pattern – Strategy
Java Program to Implement Maximum Length Chain of Pairs
Spring WebClient Requests with Parameters
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Java Program to Implement RoleUnresolvedList API
Number Formatting in Java
Map Interface trong java
Phương thức tham chiếu trong Java 8 – Method References
Guava Collections Cookbook
Documenting a Spring REST API Using OpenAPI 3.0
Send an email using the SMTP protocol
Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers
Circular Dependencies in Spring
OAuth2 Remember Me with Refresh Token
Mảng (Array) trong Java
Xây dựng ứng dụng Client-Server với Socket trong Java
Working with Kotlin and JPA
Java Program to find the number of occurrences of a given number using Binary Search approach
Introduction to Java 8 Streams
Spring Security Custom AuthenticationFailureHandler
Testing an OAuth Secured API with Spring MVC
Prevent Cross-Site Scripting (XSS) in a Spring Application
Java Copy Constructor
Java Program to Implement Binomial Tree
Java Program to Check if a Directed Graph is a Tree or Not Using DFS