Sunday, February 16, 2014

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();
}
}
}


No comments:

Post a Comment