This is a Java Program to implement Leftist Heap. A leftist heap is a priority queue implemented with a variant of a binary heap. Every node has an s-value which is the distance to the nearest leaf. In contrast to a binary heap, a leftist tree attempts to be very unbalanced. In addition to the heap property, leftist trees are maintained so the right descendant of each node has the lower s-value.
Here is the source code of the Java program to implement Leftist Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement LeftistHeap **/ import java.util.Scanner; /** Class LeftHeapNode **/ class LeftHeapNode { int element, sValue; LeftHeapNode left, right; public LeftHeapNode(int ele) { this(ele, null, null); } public LeftHeapNode(int ele, LeftHeapNode left, LeftHeapNode right) { this.element = ele; this.left = left; this.right = right; this.sValue = 0; } } /** Class LeftistHeap **/ class LeftistHeap { private LeftHeapNode root; /** Constructor **/ public LeftistHeap() { root = null; } /** Check if heap is empty **/ public boolean isEmpty() { return root == null; } /** Make heap empty **/ public void clear( ) { root = null; } /** Function to insert data **/ public void insert(int x ) { root = merge(new LeftHeapNode( x ), root); } /** Function merge **/ public void merge(LeftistHeap rhs) { if (this == rhs) return; root = merge(root, rhs.root); rhs.root = null; } /** Function merge **/ private LeftHeapNode merge(LeftHeapNode x, LeftHeapNode y) { if (x == null) return y; if (y == null) return x; if (x.element > y.element) { LeftHeapNode temp = x; x = y; y = temp; } x.right = merge(x.right, y); if(x.left == null) { x.left = x.right; x.right = null; } else { if(x.left.sValue < x.right.sValue) { LeftHeapNode temp = x.left; x.left = x.right; x.right = temp; } x.sValue = x.right.sValue + 1; } return x; } /** Function to delete minimum element **/ public int deleteMin( ) { if (isEmpty() ) return -1; int minItem = root.element; root = merge(root.left, root.right); return minItem; } /** Inorder traversal **/ public void inorder() { inorder(root); System.out.println(); } private void inorder(LeftHeapNode r) { if (r != null) { inorder(r.left); System.out.print(r.element +" "); inorder(r.right); } } } /** Class LeftistHeapTest **/ public class LeftistHeapTest { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.println("LeftistHeap Test\n\n"); LeftistHeap lh = new LeftistHeap(); char ch; /** Perform LeftistHeap operations **/ do { System.out.println("\nLeftist Heap Operations\n"); System.out.println("1. insert "); System.out.println("2. delete min"); System.out.println("3. check empty"); System.out.println("4. clear"); int choice = scan.nextInt(); switch (choice) { case 1 : System.out.println("Enter integer element to insert"); lh.insert( scan.nextInt() ); break; case 2 : lh.deleteMin(); break; case 3 : System.out.println("Empty status = "+ lh.isEmpty()); break; case 4 : lh.clear(); break; default : System.out.println("Wrong Entry \n "); break; } /** Display heap **/ System.out.print("\nInorder Traversal : "); lh.inorder(); System.out.println("\nDo you want to continue (Type y or n) \n"); ch = scan.next().charAt(0); } while (ch == 'Y'|| ch == 'y'); } }
LeftistHeap Test Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 24 Inorder Traversal : 24 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 6 Inorder Traversal : 24 6 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 19 Inorder Traversal : 24 6 19 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 94 Inorder Traversal : 24 6 94 19 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 5 Inorder Traversal : 24 6 94 19 5 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 1 Enter integer element to insert 63 Inorder Traversal : 24 6 94 19 5 63 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 2 Inorder Traversal : 94 19 63 6 24 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 2 Inorder Traversal : 94 19 63 24 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 2 Inorder Traversal : 63 24 94 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 2 Inorder Traversal : 94 63 Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 4 Inorder Traversal : Do you want to continue (Type y or n) y Leftist Heap Operations 1. insert 2. delete min 3. check empty 4. clear 3 Empty status = true Inorder Traversal : Do you want to continue (Type y or n) n
Related posts:
Java Program to Create a Random Graph Using Random Edge Generation
Java Program to Check whether Directed Graph is Connected using BFS
Java Program to Implement the MD5 Algorithm
Toán tử instanceof trong java
A Guide to JUnit 5
Java Program to Implement Park-Miller Random Number Generation Algorithm
Guava Collections Cookbook
Stack Memory and Heap Space in Java
Java Program to Implement Suffix Tree
Simultaneous Spring WebClient Calls
Number Formatting in Java
The “final” Keyword in Java
Guide to Spring 5 WebFlux
Hướng dẫn Java Design Pattern – Bridge
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Hướng dẫn sử dụng lớp Console trong java
Generic Constructors in Java
wait() and notify() Methods in Java
Xử lý ngoại lệ trong Java (Exception Handling)
Form Validation with AngularJS and Spring MVC
Java Program to Implement Gauss Seidel Method
Using Optional with Jackson
Checked and Unchecked Exceptions in Java
How to Get All Dates Between Two Dates?
Finding the Differences Between Two Lists in Java
Custom JUnit 4 Test Runners
Spring Cloud – Bootstrapping
Sending Emails with Java
New Features in Java 13
Java Program to Implement Gift Wrapping Algorithm in Two Dimensions
Java Program to Implement Ternary Search Algorithm
Converting a Stack Trace to a String in Java