DATA STRUCTURE ME LAB PROGRAMS-->3.LEFTIST HEAP

LEFTIST HEAP

Program Coding:

import java.io.*;

 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) // Hook v directly to u

      u.right = v;

    else // Merge recursively

      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 test()

  {

    if (test_heap())

      System.out.println("Heap property        ok");

    else

      System.out.println("Heap property    NOT ok !!!");

    if (test_npl())

      System.out.println("npl values           ok");

    else

      System.out.println("npl values       NOT ok !!!");

    if (test_leftist())

      System.out.println("Leftist property     ok");

   

else

      System.out.println("Leftist property NOT ok !!!");

  }

 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) // Also covers case of single node

        root = root.left;

      else

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

      return x;

    }

  }

  void test()

  {

    if (root == null)

      System.out.println("Empty heap, trivially ok");

    else

      root.test();

  }

 

  void print()

  {

    if (root == null)

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

    else

    {

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

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

      root.print(0);

    }

  }

}

 public class LeftistHeapMain

{

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

  {

    LeftistHeap heap = new LeftistHeap();

    int max,i,item;

    DataInputStream d=new DataInputStream(System.in);

    System.out.print("Enter the maximum number of nodes : ");

    max=Integer.parseInt(d.readLine());

    System.out.println("Enter the elements one by one : ");

    for(i=0;i<max;i++)

    {

        item=Integer.parseInt(d.readLine());

        heap.insert(item);

    }

    heap.print();

    System.out.println("\n\nDeleting the min element : ");

    heap.deleteMin();

    heap.print();   

    System.out.println("\n\nTesting all the properties :");

    heap.test();

    heap.print();   

    System.out.println();

  }

}

 

Output:

LEFTIST HEAP:

Enter the maximum no.of nodes:

3

Enter the elements one by one:

6

5

9

Printing all nodes:

root:

depth= =0,key= =5

left:

depth= =1,key= =6

right:

depth= =1,key= =9

Deleting minimum element:

Printing all nodes:

root:

depth= =0,key= =6

right:

depth= =1,key= =9

Testing all the properties:

Heap property ok

npl values ok

Leftist property ok

Printing all nodes:

root:

depth= =0,key= =6

right:

depth= =1,key= =9