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

Similar Programs Chapter Last Updated
HashMap Implementation In Java Data Structures 07-07-2018
Linked List Implementation In Java Data Structures 09-03-2018
Queue Implementation In Java Data Structures 22-09-2018
Stack Implementation In Java Data Structures 22-09-2018
Binary Search Tree Java Data Structures 11-02-2018
Insertion Sort In Java Data Structures 10-02-2018
Java Stack Example Data Structures 16-10-2017
Java String Array Sort Data Structures 31-03-2017
Java Hashmap Add Key And Value Data Structures 25-03-2017
Java Binary Tree Vertical Sum Data Structures 11-11-2016
Java Binary Tree Boundary Traversal Data Structures 11-11-2016
Java Binary Tree Lowest Common Ancestor (LCA) Data Structures 11-11-2016
Java Binary Tree Maximum Element Data Structures 11-11-2016
Java Three Dimensional Array Data Structures 28-10-2016
Java Infix Expression To Postfix Expression Data Structures 25-10-2016
Java Linked List Add Element First And Last Data Structures 24-10-2016
Java Maximum Element From Vector Data Structures 24-10-2016
Java Binary Search On Vector Data Structures 24-10-2016
Java Get Elements Of LinkedList Data Structures 23-10-2016
Java Linked List Update Element Data Structures 23-10-2016
Java Delete Elements From LinkedList Data Structures 23-10-2016
Java Double Ended Queue Data Structures 09-10-2016
Java Dynamic Queue Using Array Data Structures 26-09-2018
Java Queue Array Based Implementation Data Structures 07-10-2016
Java Sort Short Array Data Structures 25-09-2016
Java Sort Long Array Data Structures 25-09-2016
Java Sort Int Array Data Structures 19-09-2016
Java Sort Float Array Data Structures 19-09-2016
Java Sort Double Array Data Structures 19-09-2016
Java Sort Char Array Data Structures 19-09-2016

1 2 3