LEFTIST HEAP

AIM

To implement the leftist heap with insert and deletemin operation using Java.

ALGORITHM

Step 1:              Start the program by defining function.

Step 2:              We know heap as the root node with minimum element.

Step 3:              The insert and delete operations are performed with the help of combining 2 trees.

Step 4:              The insert operation is performed by combining the two leftist trees.

Step 5:              The deletemin() is used to delete the minimum element in the heap.

Step 6:              After the insert and delete operations leftist heap elements are displayed.

Step 7:              Stop the program.

PROGRAM

LEFTIST HEAP

import java.io.*;

class node

{

      public int data;

      public node LC,RC;

      public int shortest;

}

class minleftist

{    

      node root = null;

      public void insert()

      {

                int newelt=0;

                try

                {

                System.out.println("Enter the element:");

                DataInputStream din=new DataInputStream(System.in);

                newelt=Integer.parseInt(din.readLine());

                }

                catch(Exception e){}

                node temp = new node();

                temp.data=newelt;

                temp.LC=temp.RC=null;

                temp.shortest=1;

                if(root==null)

                root=temp;

                else

                root=meld(root,temp);

      }

      public node meld(node  a, node  b)

      {

            if(a.data > b.data)

            {

                  node  t;

                  t=a;

                  a=b;

                  b=t;

            }

            if(a.RC==null)

                  a.RC=b;

            else

                  a.RC=meld(a.RC,b);

            if((a.LC==null) || (a.LC.shortest < a.RC.shortest))

            {

                  node  t=new node();

                  t=a.LC;

                  a.LC=a.RC;

                  a.RC=t;

            }

            if(a.RC==null)

                  a.shortest=1;

            else

                  a.shortest=a.RC.shortest+1;

            return a;

      }

      public void remove()

      {

            System.out.println("Deleted element is "+root.data+"\n");

            root=meld(root.LC,root.RC);

      }

      public void display()

      {

            if(root==null)

                   System.out.println("EMPTY");

                else

                {

                System.out.println("\nIn Order");

                dispin(root);

                }

      }

      public void dispin(node currentnode)

      {

            if(currentnode!=null)

             {

            dispin(currentnode.LC);

System.out.println(currentnode.data+" "+"SHORTEST "+currentnode.shortest);

            dispin(currentnode.RC);

             }

        }

};

LEFTIST HEAP

LeftistHeapTree.java

import java.io.*;

import java.util.Date;

import java.util.Random;

class Node

{

int  key;

int  npl;

Node right;

Node left;

public Node(int key, Node left, Node right)

{

this.key   = key;

this.right = right;

this.left  = left;

}

public Node(int key)

{

this(key, null, null);

}

static Node merge(Node u, Node v)

{

if (u.key > v.key)

{

Node dummy = u; u = v; v = dummy;

}

if (u.right == null) u.right = v;

else u.right = merge(u.right, v);

if (u.left == null || u.right.npl > u.left.npl)

{

Node dummy = u.right; u.right = u.left; u.left = dummy;

}

if (u.right == null)

u.npl = 0;

else

u.npl = min(u.left.npl, u.right.npl) + 1;

return u;

}

static int min(int x, int y)

{

if (x <= y)

return x;

return y;

}

boolean test_heap()

{

if (right == null && left == null)

return true;

if (left == null)

return key <= right.key && right.test_heap();

if (right == null)

return key <= left.key && left.test_heap();

return key <= min(right.key, left.key) &&

left.test_heap() && right.test_heap();

}

boolean test_npl()

{

if (right == null || left == null)

return npl == 0;

return npl == min(left.npl, right.npl) + 1 &&

left.test_npl() && right.test_npl();

}

boolean test_leftist()

{

if (right == null)

return true;

if (left == null)

return false;

return right.npl <= left.npl &&

left.test_leftist() && right.test_leftist();

}

void print(int d)

{

System.out.println("depth == " + d + ", key == " + key);

if (left != null)

{

System.out.print("Left:  ");

left.print(d + 1);

}

if (right != null)

{

System.out.print("Right: ");

right.print(d + 1);

}

}

}

class LeftistHeap

{

Node root;

public LeftistHeap()

{

root = null;

}

public void insert(int key)

{

if (root == null)

root = new Node(key);

else

root = Node.merge(root, new Node(key));

}

public int deleteMin()

{

if (root == null)

{

System.out.println("EMPTY HEAP !!!");

return Integer.MAX_VALUE;

}

else

{

int x = root.key;

if (root.right == null)

root = root.left;

else

root = Node.merge(root.left, root.right);

return x;

}

}

void print()

{

if (root == null)

System.out.println("\nEmpty tree");

else

{

System.out.println("\nPRINTING ALL NODES:");

System.out.print("Root:  ");

root.print(0);

}

System.out.println();

}

}

public class LeftistHeapTest

{

public static void main(String[] args)throws IOException

{

LeftistHeap heap = new LeftistHeap();

System.out.println("—leftist Heap--");

int item,f,choice=1;

System.out.println("1. Insertion");

System.out.println("2. Deletion");

System.out.println("3. Exit..");

while(choice<3)

{

System.out.println("Enter your choice:");

InputStreamReader in1=new InputStreamReader(System.in);

BufferedReader br1=new BufferedReader(in1);

String s1=br1.readLine();

choice=Integer.parseInt(s1);

switch(choice)

{

case 1:

System.out.println("Enter the number of elements");

int size=Integer.parseInt(br1.readLine());

for(int i=0;i<=size-1;i++)

{

System.out.println("Enter the values to insert");

int elements=0;

elements=Integer.parseInt(br1.readLine());

heap.insert(elements);

}

break;

case 2:

int itemd=heap.deleteMin();

System.out.println("The deleted item is :  "+itemd);

break;

case 3:

break;

}

heap.print();

}

}

}