Min-Ordered Bionomial Heap Insertion java

Posted by Charodd Richardson on Stack Overflow See other posts from Stack Overflow or by Charodd Richardson
Published on 2013-10-29T03:49:59Z Indexed on 2013/10/29 3:53 UTC
Read the original article Hit count: 128

Filed under:

Im writing a java code to make a min-ordered Binomial Heap and I have to Insert and Remove-min. I'm having a very big problem inserting into the Heap. I have been stuck on this for a couple of days now and it is due tomorrow. Whenever I go to insert, It only prints out the item I insert instead of the whole tree (which is in preorder). Such as if I insert 1 it prints (1) and then I go to insert 2 it prints out (2) instead of (1(2)) It keeps printing out only the number I insert last instead of the whole preordered tree. I would be very grateful if someone could help me with this problem. Thank you so much in advance, Here is my code.

public class BHeap {

int key;
int degree;//The degree(Number of children)
BHeap parent, leftmostChild, rightmostChild, rightSibling,root,previous,next;
public BHeap(){
    key =0;
    degree=0;
    parent =null;
    leftmostChild=null;
    rightmostChild=null;
    rightSibling=null;
    root=null;
    previous=null;
    next=null;
}
public BHeap merge(BHeap x, BHeap y){
    BHeap newHeap = new BHeap();
    y.rightSibling=x.root;
    BHeap currentHeap = y;
    BHeap nextHeap = y.rightSibling;
    while(currentHeap.rightSibling !=null){
        if(currentHeap.degree==nextHeap.degree){
            if(currentHeap.key<nextHeap.key){
                if(currentHeap.degree ==0){
                    currentHeap.leftmostChild=nextHeap;
                    currentHeap.rightmostChild=nextHeap;
                    currentHeap.rightSibling=nextHeap.rightSibling;
                    nextHeap.rightSibling=null;
                    nextHeap.parent=currentHeap;
                    currentHeap.degree++;
                }
                else{
                    newHeap = currentHeap;
                    newHeap.rightmostChild.rightSibling=nextHeap;
                    newHeap.rightmostChild=nextHeap;
                    nextHeap.parent=newHeap;
                    newHeap.degree++;
                    nextHeap.rightSibling=null;
                    nextHeap=newHeap.rightSibling;
                }
            }
            else{
                if(currentHeap.degree==0){
                    nextHeap.rightmostChild=currentHeap;
                    nextHeap.rightmostChild.root = nextHeap.rightmostChild;//add
                    nextHeap.leftmostChild=currentHeap;
                    nextHeap.leftmostChild.root = nextHeap.leftmostChild;//add
                    currentHeap.parent=nextHeap;
                    currentHeap.rightSibling=null;
                    currentHeap.root=currentHeap;//add
                    nextHeap.degree++;
                }
                else{
                    newHeap=nextHeap;
                    newHeap.rightmostChild.rightSibling=currentHeap;
                    newHeap.rightmostChild=currentHeap;
                    currentHeap.parent= newHeap;
                    newHeap.degree++;
                    currentHeap=newHeap.rightSibling;
                    currentHeap.rightSibling=null;
                }
            }
        }
        else{
            currentHeap=currentHeap.rightSibling;
            nextHeap=nextHeap.rightSibling;
        }
    }
    return y;
}
public void Insert(int x){
    /*BHeap newHeap = new BHeap();
    newHeap.key=x;
    if(this.root==null){
        this.root=newHeap;
        return;
    }
    else{
        this.root=merge(newHeap,this.root);
    }*/
    BHeap newHeap= new BHeap();
    newHeap.key=x;
    if(this.root==null){
        this.root=newHeap;
    }
    else{
        this.root = merge(this,newHeap);
    }}
public void RemoveMin(){
    BHeap newHeap = new BHeap(); 
    BHeap child = new BHeap();
    newHeap=this;
    BHeap pos = newHeap.next;
    while(pos !=null){
        if(pos.key<newHeap.key){
            newHeap=pos;
        }
        pos=pos.rightSibling;
    }
    pos=this;
    BHeap B1 = new BHeap();
    if(newHeap.previous!=null){
        newHeap.previous.rightSibling=newHeap.rightSibling;
        B1 =pos.leftmostChild;
        B1.rightSibling=pos;
        pos.leftmostChild=pos.rightmostChild.leftmostChild;
    }
    else{
        newHeap=newHeap.rightSibling;
        newHeap.previous.rightSibling=newHeap.rightSibling;
        B1 =pos.leftmostChild;
        B1.rightSibling=pos;
        pos.leftmostChild=pos.rightmostChild.leftmostChild;
    }
    merge(newHeap,B1);
}
public void Display(){

    System.out.print("(");
    System.out.print(this.root.key);
    if(this.leftmostChild != null){
        this.leftmostChild.Display();
    }
    System.out.print(")");
    if(this.rightSibling!=null){
        this.rightSibling.Display();
    }
}

}

© Stack Overflow or respective owner

Related posts about java