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:
Introduction to Spring Data JDBC
Java Program to Implement EnumMap API
Guide to the Synchronized Keyword in Java
Query Entities by Dates and Times with Spring Data JPA
Java Program to Implement Shell Sort
Feign – Tạo ứng dụng Java RESTful Client
Unsatisfied Dependency in Spring
Java Program to Perform Insertion in a BST
Spring 5 Functional Bean Registration
Java Program to Perform Left Rotation on a Binary Search Tree
Java Program to Check if any Graph is Possible to be Constructed for a Given Degree Sequence
Guide to Apache Commons CircularFifoQueue
Quick Guide to the Java StringTokenizer
Spring Webflux and CORS
Tạo ứng dụng Java RESTful Client với thư viện Retrofit
Spring WebClient and OAuth2 Support
Mix plain text and HTML content in a mail
Java Program to Implement Vector API
Tìm hiểu về Web Service
How to Use if/else Logic in Java 8 Streams
Working with Kotlin and JPA
Converting Between Byte Arrays and Hexadecimal Strings in Java
Java Program to Construct an Expression Tree for an Prefix Expression
Java Program to Check Whether an Undirected Graph Contains a Eulerian Cycle
Spring Boot - Admin Server
Static Content in Spring WebFlux
Exploring the New Spring Cloud Gateway
Tính đóng gói (Encapsulation) trong java
Java Program to Generate Date Between Given Range
Guide to the Java TransferQueue
Request a Delivery / Read Receipt in Javamail
Java Program to Decode a Message Encoded Using Playfair Cipher