// ModifiedHeap class
   
public class ModifiedHeap
{

    private ModifiedHeapNode root;    // root

    //Construct the modified heap - start with an empty heap.
    public ModifiedHeap ( )
    {
        root = null;
    }

    public ModifiedHeap(ModifiedHeapNode h) {
	root = h;
    }


    // public join function which joins 
    // rightHeap (passed in parameter)
    // to this heap.
    // If you follow the algorithm given in the handout,
    // rightHeap becomes empty after join() is over
    public void join (ModifiedHeap rightHeap)
    {
	// avoid joining of the same tree with itself
    	if( this == rightHeap )
    	    return;

       //otherwise a join is just joining two nodes recursively
	root = joinR( root, rightHeap.root );

    //this line is needed for garbage collection
    //not required for assignment - but technically correct
    rightHeap.root = null;
    }


    // private join function that joins h1 and h2 (one or both could be null)
    // and returns the joined heap.
    // If you follow the algorithm in the handout, one of h1 and h2
    // will become the joined heap and the other will become an empty
    // heap.
    private ModifiedHeapNode joinR (ModifiedHeapNode h1, ModifiedHeapNode h2)
    {

 //Easy cases - when one heap is null
     if( h1 == null )
	return h2;
    if( h2 == null )
	return h1;


    //otherwise - test which heap has smaller max

    //1st case h2 has smaller max elelemnt
    if( h1.element > h2.element ) {
	

	//if h1 is a single node
	//add to left to keep left weightwed heap height
	if( h1.left == null )   // Single node
	    h1.left = h2;       // Other fields in h1 already accurate
	

	//otherwise there is work to do
	//which is to recrursively join h1's right child to h2
	else {
	    h1.right = joinR( h1.right, h2 );
	   
	    //after recursion unravels
	    //check heap height to see if there is a fix
	    //if there is swap the children
	    if( h1.left.heapHeight < h1.right.heapHeight )
                    swapChildren( h1 );

	    //fix heap height
	    h1.heapHeight = h1.right.heapHeight + 1;
	}
	return h1;
    }

    //otherwise whole code above is same with h1 swapped for h2
    //since exaclty the same function happens
    //except with h1 and h2's right child

    else {
	if( h2.left == null )   // Single node
	    h2.left = h1;       // Other fields in h1 already accurate
	else {
	    h2.right = joinR( h2.right, h1 );
	    if( h2.left.heapHeight < h2.right.heapHeight )
                    swapChildren( h2 );
	    h2.heapHeight = h2.right.heapHeight + 1;
	}
	return h2;
    }
    }

    // Swaps a nodes two children - use this to maintain proper heap height.
    private void swapChildren ( ModifiedHeapNode t )
    {
        ModifiedHeapNode tmp = t.left;
        t.left = t.right;
        t.right = tmp;
    }

    // Insert x into the heap, maintaining heap order.
    public void insert (int x)
    {
	//insert is just a join with a new node and root
       	  root = joinR( new ModifiedHeapNode( x ), root );
    }

    // Method to remove the largest item from the heap.
    // and return the largest key (an int)
    // If the heap is empty return the smallest possible (negative) int.
    // The smallest possible negative int is given by Integer.MIN_VALUE
    public int deleteMax ( )
    {
	// If the heap is empty return an error - i.e smallest int
	//same as normal heap
         if(isEmpty())
	     return Integer.MIN_VALUE;


	 
	 //otherwise return the element stored at root
	 //and simply join the left and right heaps rooted at the
	 //root's left and right children
	 
	 else {
	 
	     int mItem = root.element;
	     root = joinR( root.left, root.right );
	     return mItem;

	 }
    }
  
    // Test if heap is empty
    public boolean isEmpty ( )
    {
        return (root == null);
    }

    // print the heap
    // Inorder traversal
    public void print ()
    {
	System.out.print ("Heap: ");
	inorder (root);
	System.out.println ();
    }

    private void inorder (ModifiedHeapNode t)
    {
	if (t == null)
	    return;
	System.out.print ("[ ");
System.out.print (t.element + " ");
	inorder (t.left);
	
	inorder (t.right);
	System.out.print ("] ");
    }
}