public class BinomialHeap
{
    static int MIN=-5000;
    public BinomialHeap()
    {
    }
    public BHNode insert (BHNode head,Node node)
    {
      BHNode head1=new BHNode();
        head1.node=node;
        head1.parent=null;
        head1.child=null;
        head1.prev=head1.next=head1;
        head1.outdegree=0;
        head1.last=true;
    return merge(head,head1);
    }

    public Node returnMin (BHNode head)
    {
        
        BHNode s=head;  
        BHNode min=head;;
        while(s!=null && !s.last)
        {
            if(s.node.returnkey()<min.node.returnkey())
                min=s;
            s=s.next;
        }       
        return min.node;
    }
    public BHNode deleteMin (BHNode head)
    {
        BHNode s=head;  
        BHNode min=head;;
        while(s!=null && !s.last)
        {
            if(s.node.returnkey()<min.node.returnkey())
                min=s;
            s=s.next;
        }       
        min.prev.next=min.next;
        min.next.prev=min.prev;
        min.child.parent=null;
        return merge(head,min.child);
    }
    
    public BHNode link(BHNode head1,BHNode head2)
    {
        if(head1.outdegree!=head2.outdegree)
            return null;
        
        BHNode parent,child;
        if(head1.node.returnkey()<=head2.node.returnkey())
        {
            parent=head1; 
            child=head2;
        }
        else
        {
            parent=head2;
            child=head1;
        }
        
        parent=head1;
        child=head2;
        
        if(parent.child!=null)
        {
        BHNode lastchild=parent.child.prev;
        lastchild.next=child;
        child.next=parent.child;
        child.prev=lastchild;
        parent.child.prev=child;
        lastchild.last=false;
            
        }
        else
        {
            parent.child=child;
            child.next=child.prev=child;
        }

        child.parent=parent;
        child.last=true;
        parent.outdegree++;
        return parent;
    }
    
    public BHNode merge(BHNode head1,BHNode head2)
    {
        //____do binary addition
        BHNode mhead;
        BHNode t=null;
        
        debug("displaying the heaps");
        //____Display Initial heaps___
        System.out.println("\nHeap 1 :");
        display(head1,0);
        System.out.println("\nHeap 2 :");
        display(head2,0);
        debug("checking for null cond");        
        if(head1==null)
        {
            mhead=head2;
            return mhead;
        }   
        if(head2==null)
        {
            mhead=head1;
            return mhead;
        }   

        debug("starting semi-merging");         

        mhead=new BHNode();
        t=mhead;
        debug("starting semi-merging");         

        
        int flag=0;
        do
        {                   
            if(t.node!=null)
                System.out.println("Key : " + t.node.returnkey());
                
            if((flag%2)!=1 && (head1.outdegree<=head2.outdegree || flag==2))
            {
                t.next=head1;
                if(head1.last)
                    flag=flag | 1;
                head1=head1.next;
            }
            else if(flag<2 && (head2.outdegree<=head1.outdegree || (flag%2)==1))
            {
                t.next=head2;
                if(head2.last)
                    flag=flag | 2;
                head2=head2.next;
            }
            t.next.prev=t;
            t=t.next;
            t.last=false;
        }while((flag & 3)<3);
        debug("semi-merged");
        mhead=mhead.next;
        t.prev.last=false;
        t.last=true;
        t.next=mhead;
        mhead.prev=t;
        //____Now all the heaps are in increasing order_____
        System.out.println("\nNow displaying the merged heap in merging\n");
        display(mhead,0);
                t=mhead;
        BHNode oldt=null;
        while(t.last==false)
        {
            if(t.outdegree!=t.next.outdegree || 
                (t.next.next.outdegree==t.next.outdegree && t.next.last==false))
            {
                oldt=t;
                t=t.next;
            }
            else
            {
                if(t.node.returnkey()<=t.next.node.returnkey())
                {
                    
                System.out.println("merging...1");
                    t.last=t.next.last;
                    BHNode oldnext=t.next.next;
                    link(t,t.next);
                    t.next=oldnext; 
                }
                else
                {
                    System.out.println("merging...2");
                    if(oldt==null)
                        mhead=t.next;
                    else
                        oldt.next=t.next;
                    
                    BHNode oldtnext=t.next;
                    link(t.next,t);
                    if(oldtnext.last)
                        oldtnext.next=mhead;
                        t=oldtnext;
                    debug("display finished");
                }
            }
            debug("infinite");
        }
        t.last=true;
        t.next=mhead;
        //____Have to consider last more carefully!!
        debug("prev point");
        //_____Update prev pointers
        t=mhead;
        while(t.last==false)
        {
            t.next.prev=t;
            t=t.next;
        }
            
        mhead.prev=t;
        System.out.println("\nNow displaying the final heap in merging\n");
        display(mhead,0);
        debug("Merge completed");
        return mhead;
    }
    public void debug(String str)
    {
        System.out.println(str);
        System.out.flush();
    }
    public void display(BHNode head,int space)
    {
        if(head==null) 
            return;
        BHNode t=head;
        do
        {
        //  debug("infinite");
            int i;
            for(i=0;i<space;i++)
                System.out.print(" ");
            System.out.println(t.node.returnkey());
            display(t.child,space+2);
            t=t.next;
        }while(t!=head);
    }
                    
}