Java Program To Implement Meldable Heap

Chapter: Data Structures Last Updated: 13-07-2016 09:57:22 UTC

Program:

            /* ............... START ............... */
                
import java.util.Scanner;
import java.util.Random;

class Node {
	Node left, right, parent;
	int x;

	public Node(Node parent, Node left, Node right, int x) {
		this.parent = parent;
		this.left = left;
		this.right = right;
		this.x = x;
	}
}

class MeldableHeap {
	private Random rand;
	private int n;
	private Node root;

	public MeldableHeap() {
		root = null;
		rand = new Random();
		n = 0;
	}

	public boolean isEmpty() {
		return root == null;
	}

	public void makeEmpty() {
		root = null;
		rand = new Random();
		n = 0;
	}

	public int getSize() {
		return n;
	}

	public void add(int x) {
		Node u = new Node(null, null, null, x);
		root = meld(u, root);
		root.parent = null;
		n++;
	}

	public int remove() {
		int x = root.x;
		root = meld(root.left, root.right);
		if (root != null)
			root.parent = null;
		n--;
		return x;
	}

	public Node meld(Node q1, Node q2) {
		if (q1 == null)
			return q2;
		if (q2 == null)
			return q1;

		if (q2.x < q1.x)
			return meld(q2, q1);

		if (rand.nextBoolean()) {
			q1.left = meld(q1.left, q2);
			q1.left.parent = q1;
		} else {
			q1.right = meld(q1.right, q2);
			q1.right.parent = q1;
		}
		return q1;
	}

	public void displayHeap() {
		System.out.print("\nMeldable Heap : ");
		if (root == null) {
			System.out.print("Empty\n");
			return;
		}

		Node prev, w = root;
		while (w.left != null)
			w = w.left;

		while (w != null) {
			System.out.print(w.x + " ");
			prev = w;
			w = nextNode(w);
		}
		System.out.println();
	}

	private Node nextNode(Node w) {
		if (w.right != null) {
			w = w.right;
			while (w.left != null)
				w = w.left;
		} else {
			while (w.parent != null && w.parent.left != w)
				w = w.parent;
			w = w.parent;
		}
		return w;
	}
}

public class JavaMeldableHeapExample {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		System.out.println("Meldable Heap Test\n\n");

		MeldableHeap mh = new MeldableHeap();

		char ch;
		do {
			System.out.println("\nMeldable Heap Operations\n");
			System.out.println("1. add");
			System.out.println("2. remove");
			System.out.println("3. size");
			System.out.println("4. check empty");
			System.out.println("5. clear");

			int choice = scan.nextInt();
			switch (choice) {
			case 1:
				System.out.println("Enter integer element to insert");
				mh.add(scan.nextInt());
				break;
			case 2:
				System.out.println("Removed Element : " + mh.remove());
				break;
			case 3:
				System.out.println("Size = " + mh.getSize());
				break;
			case 4:
				System.out.println("Empty status = " + mh.isEmpty());
				break;
			case 5:
				mh.makeEmpty();
				System.out.println("Heap Cleared\n");
				break;
			default:
				System.out.println("Wrong Entry \n ");
				break;
			}

			mh.displayHeap();

			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

Meldable Heap Test



Meldable Heap Operations

1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
1

Meldable Heap : 1 

Do you want to continue (Type y or n) 

y

Meldable Heap Operations

1. add
2. remove
3. size
4. check empty
5. clear
1
Enter integer element to insert
2

Meldable Heap : 2 1 

Do you want to continue (Type y or n) 

y

Meldable Heap Operations

1. add
2. remove
3. size
4. check empty
5. clear
2
Removed Element : 1

Meldable Heap : 2 

Do you want to continue (Type y or n) 

n

Notes:

  • A randomized meldable heap (also Meldable Heap or Randomized Meldable Priority Queue) is a priority queue based data structure in which the underlying structure is also a heap-ordered binary tree.

Tags

Implement Meldable 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