Java Program To Implement Leftist Heap
Chapter:
Data Structures
Last Updated:
13-07-2016 09:18:24 UTC
Program:
/* ............... START ............... */
import java.util.Scanner;
class LeftHeapNode {
int element, sValue;
LeftHeapNode left, right;
public LeftHeapNode(int ele) {
this(ele, null, null);
}
public LeftHeapNode(int ele, LeftHeapNode left, LeftHeapNode right) {
this.element = ele;
this.left = left;
this.right = right;
this.sValue = 0;
}
}
class LeftistHeap {
private LeftHeapNode root;
public LeftistHeap() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void clear() {
root = null;
}
public void insert(int x) {
root = merge(new LeftHeapNode(x), root);
}
public void merge(LeftistHeap rhs) {
if (this == rhs)
return;
root = merge(root, rhs.root);
rhs.root = null;
}
private LeftHeapNode merge(LeftHeapNode x, LeftHeapNode y) {
if (x == null)
return y;
if (y == null)
return x;
if (x.element > y.element) {
LeftHeapNode temp = x;
x = y;
y = temp;
}
x.right = merge(x.right, y);
if (x.left == null) {
x.left = x.right;
x.right = null;
} else {
if (x.left.sValue < x.right.sValue) {
LeftHeapNode temp = x.left;
x.left = x.right;
x.right = temp;
}
x.sValue = x.right.sValue + 1;
}
return x;
}
public int deleteMin() {
if (isEmpty())
return -1;
int minItem = root.element;
root = merge(root.left, root.right);
return minItem;
}
public void inorder() {
inorder(root);
System.out.println();
}
private void inorder(LeftHeapNode r) {
if (r != null) {
inorder(r.left);
System.out.print(r.element + " ");
inorder(r.right);
}
}
}
public class JavaLeftistHeapExample {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("LeftistHeap Test\n\n");
LeftistHeap lh = new LeftistHeap();
char ch;
do {
System.out.println("\nLeftist Heap Operations\n");
System.out.println("1. insert ");
System.out.println("2. delete min");
System.out.println("3. check empty");
System.out.println("4. clear");
int choice = scan.nextInt();
switch (choice) {
case 1:
System.out.println("Enter integer element to insert");
lh.insert(scan.nextInt());
break;
case 2:
lh.deleteMin();
break;
case 3:
System.out.println("Empty status = " + lh.isEmpty());
break;
case 4:
lh.clear();
break;
default:
System.out.println("Wrong Entry \n ");
break;
}
/** Display heap **/
System.out.print("\nInorder Traversal : ");
lh.inorder();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
/* ............... END ............... */
Output
LeftistHeap Test
Leftist Heap Operations
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
2
Inorder Traversal : 2
Do you want to continue (Type y or n)
y
Leftist Heap Operations
1. insert
2. delete min
3. check empty
4. clear
1
Enter integer element to insert
3
Inorder Traversal : 3 2
Do you want to continue (Type y or n)
y
Leftist Heap Operations
1. insert
2. delete min
3. check empty
4. clear
3
Empty status = false
Inorder Traversal : 3 2
Do you want to continue (Type y or n)
y
Leftist Heap Operations
1. insert
2. delete min
3. check empty
4. clear
4
Inorder Traversal :
Do you want to continue (Type y or n)
n
Notes:
-
A leftist heap is a priority queue implemented with a variant of a binary heap.
Tags
Implement Leftist Heap, Java, Data Structures