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>