Java Program to Implement Meldable Heap

This is a Java Program to Implement Meldable Heap. 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. However, there are no restrictions on the shape of the underlying binary tree.

Here is the source code of the Java Program to Implement Meldable Heap. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 **  Java Program to Implement Meldable Heap
 **/
 
import java.util.Scanner;
import java.util.Random;
 
/** Class Node **/
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 MedlableHeap **/
class MeldableHeap
{
    private Random rand;
    private int n;    
    private Node root;
 
    public MeldableHeap()
    {
        root = null;
        rand = new Random();
        n = 0;
    }
 
    /** Check if heap is empty **/
    public boolean isEmpty()
    {
        return root == null;
    }
 
    /** clear heap **/
    public void makeEmpty()
    {
        root = null;
        rand = new Random();
        n = 0;
    }
 
    /** function to get size **/
    public int getSize()
    {
        return n;
    }
 
    /** function to insert an element **/
    public void add(int x) 
    {
        Node u = new Node(null, null, null, x);
        root = meld(u, root);
        root.parent = null;
        n++;
    }
 
    /** function to remove an element **/
    public int remove() 
    {
        int x = root.x;
        root = meld(root.left, root.right);
        if (root != null) 
            root.parent = null;
        n--;
        return x;
    }
 
    /** function to merge two nodes **/
    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;
    }
 
    /** function to print heap **/
    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();
    }
 
    /** function to get next node in heap **/
    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;
    }    
}
 
/** Class MeldableHeapTest **/
public class MeldableHeapTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Meldable Heap Test\n\n");
 
        /* Make object of MeldableHeap */
        MeldableHeap mh = new MeldableHeap();
 
        char ch;
        /*  Perform Meldable Heap operations  */
        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;   
            }
            /* Display heap */
            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');  
    }
}

Meldable Heap Test
 
 
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
4
Empty status = true
 
Meldable Heap : Empty
 
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
24
 
Meldable Heap : 24
 
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
6
 
Meldable Heap : 24 6
 
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
28
 
Meldable Heap : 28 24 6
 
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
94
 
Meldable Heap : 28 24 6 94
 
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
19
 
Meldable Heap : 28 24 6 19 94
 
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
5
 
Meldable Heap : 28 24 6 19 94 5
 
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
63
 
Meldable Heap : 28 24 6 19 94 5 63
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
3
Size = 7
 
Meldable Heap : 28 24 6 19 94 5 63
 
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 : 5
 
Meldable Heap : 28 63 24 6 19 94
 
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 : 6
 
Meldable Heap : 28 63 24 19 94
 
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 : 19
 
Meldable Heap : 28 63 24 94
 
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 : 24
 
Meldable Heap : 94 28 63
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
5
Heap Cleared
 
 
Meldable Heap : Empty
 
Do you want to continue (Type y or n)
 
y
 
Meldable Heap Operations
 
1. add
2. remove
3. size
4. check empty
5. clear
4
Empty status = true
 
Meldable Heap : Empty
 
Do you want to continue (Type y or n)
 
n