A leftist heap is a priority Queue implemented with a binary heap. Every node has a sValue which is at the nearest Distance to the other nodes. Now we will write a java program for performing certain operations on a leftist Heap (Inorder Traversal) like insert, delete, clear, and check for empty.
A leftist tree is a binary tree with properties:
- Normal Min Heap Property : key(i) >= key(parent(i))
- Heavier on left side : dist(right(i)) <= dist(left(i)). Here, dist(i) is the number of edges on the shortest path from node i to a leaf node in extended binary tree representation (In this representation, a null child is considered as an external or leaf node). The shortest path to a descendant external node is through the right child. Every subtree is also a leftist tree and dist( i ) = 1 + dist( right( i ) ).
Example: The below leftist tree is presented with its distance calculated for each node with the procedure mentioned above. The rightmost node has a rank of 0 as the right subtree of this node is null and its parent has a distance of 1 by dist( i ) = 1 + dist( right( i )). The same is followed for each node and their s-value( or rank) is calculated.
From the above second property, we can draw two conclusions :
- The path from the root to the rightmost leaf is the shortest path from the root to the leaf.
- If the path to the rightmost leaf has x nodes, then the leftist heap has at least 2x – 1 node. This means the length of the path to the rightmost leaf is O(log n) for a leftist heap with n nodes.
Example:
LEFTIST HEAP Functions to do 2. delete min 3. check empty 4. clear 2 Inorder Traversal: 53 52 54 If you wish to continue type Y or y y Functions to do 2. delete min 3. check empty 4. clear 3 Empty status = false Inorder Traversal: 53 52 54 If you wish to continue type Y or y y Functions to do 2. delete min 3. check empty 4. clear 4 Inorder Traversal: If you wish to continue type Y or y
Approach:
- We will first take a class Node and create its constructor and various parameters.
- Then we will create a class LeftHeap, In this class, we will create various methods and try to perform their operations.
- We will create a constructor, where we keep the root null.
- We will create a method isEmpty() to check if the Heap is empty.
- We will create a method clear(), to clear the heap.
- We create a method to merge:
- Here we need to take two nodes, and then we would check for both of them being empty
- Then we would set the values right or left according to our convenience.
- This function is used to find the minimum element in the heap
- Then we declare a function named del().
- This function is used to find the minimum number, and then we remove it.
- Then we declare the main function and call the function and do operations performed with the help of a switch case. The operations performed are whether to check if it is empty or to empty the heap or delete the minimum element.
Implementation:
Java
// Java Program to Implement Leftist Heap// Declare all librariesimport java.io.*;import java.util.Scanner;// Class Nodeclass Node { // elements, and sValue are the variables in class Node int element, sValue; // class has two parameters Node left, right; public Node(int element) { this(element, null, null); } // Function Node where we are using this keyword // Which will help us to avoid confusion if we are having // same elements public Node(int element, Node left, Node right) { this.element = element; this.left = left; this.right = right; this.sValue = 0; }}// Class Left heapclass LeftHeap { // Now parameter is created named head. private Node head; // Its constructor is created named left heap // Returns null public LeftHeap() { head = null; } // Now we will write function to check if the list is // empty public boolean isEmpty() { // If head is null returns true return head == null; } // Now we will write a function clear public void clear() { // We will put head is null head = null; } // Now let us create a function merge which will // help us merge public void merge(LeftHeap rhs) { // If the present function is rhs // then we return it if (this == rhs) return; // Here we call the function merge // And make rhs is equal to null head = merge(head, rhs.head); rhs.head = null; } // Function merge with two Nodes a and b public Node merge(Node a, Node b) { // If A is null // We return b if (a == null) return b; // If b is null // we return A if (b == null) return a; // If we put a element greater than b element if (a.element > b.element) { // We write the swap code Node temp = a; a = b; b = temp; } // Now we call the function merge to merge a and b a.right = merge(a.right, b); // If a is null we swap right with left and empty // right if (a.left == null) { a.left = a.right; a.right = null; } // else // if value in a is less than the svalue of right // If the condition is satisfied , we swap the left // with right else { if (a.left.sValue < a.right.sValue) { Node temp = a.left; a.left = a.right; a.right = temp; } // we store the value in a s Value of right // SValue a.sValue = a.right.sValue + 1; } // We now return the value of a return a; } // Function insert public void insert(int a) { // This root will help us insert a new variable head = merge(new Node(a), head); } // The below function will help us delete minimum // function present in the Heap public int del() { // If is empty return -1 if (isEmpty()) return -1; // Now we will store the element in variable and // Call the merge function to del that is converging // to head then we return min int min = head.element; head = merge(head.left, head.right); return min; } // Function order // will print the starting and ending points in order. public void order() { order(head); System.out.println(); } // Function order with Node r // If r not equal to r // It prints all the elements iterating from order left // to right private void order(Node r) { if (r != null) { order(r.left); System.out.print(r.element + " "); order(r.right); } }}// Class gfgclass GFG { public static void main(String[] args) { // Creating the scanner object Scanner sc = new Scanner(System.in); System.out.println("LEFTIST HEAP"); // Creating object for class LeftHeap LeftHeap h = new LeftHeap(); // Char ch char ch; // Now taking the loop do { // Now writing down all the functions System.out.println("Functions to do"); System.out.println("1. insert"); System.out.println("2. delete min"); System.out.println("3. check empty"); System.out.println("4. clear"); // Scanning the choice to be used in switch int choice = sc.nextInt(); // Using switch switch (choice) { // Case 1 // to insert the elements in the heap // call the insert func case 1: System.out.println("Enter integer element to insert"); h.insert(sc.nextInt()); break; // Delete the minimum element in the func case 2: h.del(); break; // To check the empty status of the heap case 3: System.out.println("Empty status = " + h.isEmpty()); break; // Cleaning the heap case 4: h.clear(); break; default: System.out.println("Wrong entry"); break; } // Prints the inorder traversal // Calling the func System.out.print("\n Inorder Traversal: "); h.order(); // Whether to continue or not System.out.println("\n If you wish to continue type Y or y"); ch = sc.next().charAt(0); } // Closing of loop while (ch == 'Y' || ch == 'y'); }} |
Output:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
