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 gfgÂ
class 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!
