public class MyHeap implements PriorityQueue  {
       
       private AVLNode root;//declare the root node
        
       //Construct the AVL tree.
        public MyHeap(){
            root = null;
        }

       //Insert new item into the AVL tree.
        public void insert(double x){
            root = insert(x, root);
        }

        //Remove the minimum item from the tree and return its value.
        public double deleteMin(){    
           double temp=elementAt(findMin(root));
           deleteMin(root);
           return temp;
        }
        
        //Find and return the smallest item in the tree and return its value.
        public double findMin(){
            return elementAt(findMin(root));
        }

        /**
         * Check whether tree is empty or not 
         * return 1-->is empty 
         * return 0-->is not empty    
         */
        public boolean isEmpty(){
            return root == null;
        }

        // Erases all elements from the AVL tree.
        public void makeEmpty(){
            while(root!=null)
                deleteMin();
        }

       
        //return the element associate with node t
        private double elementAt(AVLNode t){
            return t == null ? null : t.element;
        }

        /**
         * Internal method to insert into a subtree.
         * @param x the item to insert.
         * @param t the node that roots the tree.
         * @return the new root.
         */
        private AVLNode insert(double x, AVLNode t ){
            if( t == null )
                return new AVLNode(x,null,null);
            
            if(x<t.element){
                t.left = insert(x, t.left);
                if(height(t.left)-height(t.right) == 2 )
                    if(x<t.left.element)
                        t = rotateLeft(t);
                    else
                        t = doubleRotateLeft(t);
            }
            
            else if(x>t.element){
                t.right = insert(x, t.right);
                if(height(t.right) - height(t.left) == 2)
                    if(x>t.right.element)
                        t = rotateRight(t);
                    else
                        t = doubleRotateRight(t);
            }
            
            else
                ;  // Duplicate; do nothing
            t.height = Math.max(height(t.left), height(t.right)) + 1;
            
            return t;
        }

        /**
         * private method to find the smallest item in the subtree.
         * @param t the node that roots the tree.
         */
        private AVLNode findMin(AVLNode t){
            if(t == null)
                return null;

            while(t.left != null)
                t = t.left;
            
            return t;
        }
        
        private AVLNode deleteMin(AVLNode t){
            if(t==null)
                throw new EmptyHeapException();
            else if(t.left!=null){
                t.left=deleteMin(t.left);
                if(height(t.right)-height(t.left) == 2 )
                    
                        t = rotateLeft(t);
                    else
                        t = doubleRotateLeft(t);
          
                return t;
            }
            else 
                return t.right;
        }


        //in-order traverse the AVL tree
        private void traverse(AVLNode t)
        {
            if( t != null )
            {
                traverse(t.left);
                System.out.println( t.element );
                traverse(t.right);
            }
        }

       
        //Return the height of node t, or -1, if null.
        private int height(AVLNode t){
            return t == null?-1:t.height;
        }

        
        /**
         * Rotate AVL tree node with left child.
         * this is a single rotation for case 1.
         * Update heights, then return new root.
         */
        private AVLNode rotateLeft(AVLNode root)
        {
            AVLNode temp = root.left;
            root.left = temp.right;
            temp.right = root;
            root.height = Math.max(height(root.right), height(root.left))+1;
            temp.height = Math.max(height(temp.right), height(temp.left))+1;
            root=temp;
            return root;
        }

        /**
         * Rotate AVL tree node with right child.
         * this is a single rotation for case 4.
         * Update heights, then return new root.
         */
        private AVLNode rotateRight(AVLNode root)
        {
            AVLNode temp = root.right;
            root.right = temp.left;
            temp.left = root;
            root.height = Math.max(height(root.right), height(root.left))+1;
            temp.height = Math.max(height(temp.right), height(temp.left))+1;
            root=temp;
            return root;
        }

        /**
         * Double rotate AVL tree node: first left child
         * with its right child; then root with new left child.
         * this is a double rotation for case 2.
         * Update heights, then return new root.
         */
        private AVLNode doubleRotateLeft(AVLNode root){
            root.left = rotateRight(root.left);
            return rotateLeft(root);
        }

        /**
         * Double rotate AVL tree node: first right child
         * with its left child; then root with new right child.
         * this is a double rotation for case 3.
         * Update heights, then return new root.
         */
        private AVLNode doubleRotateRight(AVLNode root){
            root.right = rotateLeft(root.right);
            return rotateRight(root);
        }
          
    }


/**
* AVLNode class used in MyHeap class
*@ Liyun Zeng
*@ 2-1-09
*/

class AVLNode{
    double element;   // The data include in the node
    AVLNode left;     // Left child reference
    AVLNode right;    // Right child reference
    int height;       // Height of this node
       
    // Constructors
    AVLNode(double theElement){
        this(theElement, null, null);
    }

    AVLNode(double theElement, AVLNode lt, AVLNode rt ){
        element  = theElement;
        left     = lt;
        right    = rt;
        height   = 0;
    }

}