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>

Edited 5 Years Ago by masijade: added code tags

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

This article has been dead for over six months. Start a new discussion instead.