import java.io.*;
import java.util.Date;
import java.util.Random;
class Clock 
{
 	static long now()
  	// returns the current time in miliseconds
  	{
    		return (new Date()).getTime();
  	}
}
class IO
{
  	static int readInt() 
  	{
    		String input = "";
   		try 
    		{
      			input=(newBufferedReader(newInputStreamReader(System.in))).readLine();
    		} 
    		catch (java.io.IOException e) 
    		{
      			System.out.println("Error while reading");
    		}
    		return Integer.valueOf(input).intValue();
  	}
}
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)
  	{
    		// Assure that the key of u is smallest
   		 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);
    		// Conditionally swap children of u
   		 if (u.left == null || u.right.npl > u.left.npl)
    		{
      			Node dummy = u.right; u.right = u.left; u.left = dummy; 
    		}
    		// Update npl values
    		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);
    		}
    		System.out.println();
  	}
}
public class LeftistHeapTest
{
public static void main(String[] args)
  	{
    		System.out.println();
    		LeftistHeap heap = new LeftistHeap();
    		System.out.print("Step by step test? (yes = 1)   >>>   ");
    		if (IO.readInt() == 1)
    		{
     			 int c = 0;
      			while (c != 5)
      			{
        				System.out.print("Give operation: 1.insert 2.delete 3.test 4.print 5.stop)   >>>   ");
        				c = IO.readInt();
        				if (c == 1)
        				{
          					System.out.print("Give key to insert   >>>   ");
          					heap.insert(IO.readInt());
        				}
        				else if (c == 2)
          					System.out.println("Deletemin returns"+ heap.deleteMin());
        				else if (c == 3)
          					heap.test();
        				else if (c == 4)
          					heap.print();
      			}
    		}
    		else // Bulk test
    		{
      			System.out.print("Give n   >>>   ");
      			int n = IO.readInt();
     			Random random = new Random(Clock.now());
      			long t = - Clock.now();
      			for (int i = 0; i < n; i++)
       				heap.insert(random.nextInt());
      			t += Clock.now();
      			if (n <= 100)
        				heap.print();
      			heap.test();
      			System.out.println(n + " inserts    took " + t + " milliseconds");
      			t = - Clock.now();
      			for (int i = 0; i < n; i++)
        				heap.deleteMin();
      			t += Clock.now();
      			System.out.println(n + " deletemins took " + t + " milliseconds");
    		}
    		System.out.println();
  	}
}

OUTPUT:

C:\j2sdk1.4.1_02\bin>javac LeftistHeapTest.java
C:\j2sdk1.4.1_02\bin>java LeftistHeapTest
Step by step test? (yes = 1) >>> 1
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 1
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 2
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 3
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 4
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 5
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 6
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 7
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 8
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 9
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 1
Give key to insert >>> 10
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 4

PRINTING ALL NODES:
Root: depth == 0, key == 1
Left: depth == 1, key == 3
Left: depth == 2, key == 4
Right: depth == 2, key == 5
Right: depth == 1, key == 2
Left: depth == 2, key == 7
Left: depth == 3, key == 8
Right: depth == 3, key == 9
Right: depth == 2, key == 6
Left: depth == 3, key == 10


Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 2
Deletemin returns 1
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 4

PRINTING ALL NODES:
Root: depth == 0, key == 2
Left: depth == 1, key == 7
Left: depth == 2, key == 8
Right: depth == 2, key == 9
Right: depth == 1, key == 3
Left: depth == 2, key == 4
Right: depth == 2, key == 5
Left: depth == 3, key == 6
Left: depth == 4, key == 10

Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 3
Heap property ok
npl values ok
Leftist property ok
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 4

PRINTING ALL NODES:
Root: depth == 0, key == 2
Left: depth == 1, key == 7
Left: depth == 2, key == 8
Right: depth == 2, key == 9
Right: depth == 1, key == 3
Left: depth == 2, key == 4
Right: depth == 2, key == 5
Left: depth == 3, key == 6
Left: depth == 4, key == 10
Give operation: 1.insert 2.delete 3.test 4.print 5.stop) >>> 5
C:\j2sdk1.4.1_02\bin>

Please use code tags.

Anyway, what is your question?

And why a Leftist heap? Why not a Marxist heap?

i want to know how insertion and deletion works in my program and how to find depth for each key

What do you mean "how insertion and deletion works in my program"? Don't you know? Didn't you write it?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.