Binomial Heap Insertion java

Question

I'm having trouble inserting into a binomial heap, When I call insert 1 it prints (1) and then I insert 2 it displays (2) instead of (1(2)) and then three it displays (3) instead of (3)(1(2)). I would be very grateful if someone could help figure out my problem. Thank you 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 y){
        BHeap newHeap = new BHeap();
        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;
        }
        else{
            this.root = merge(newHeap);
        }
    }
    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();
        }
    }
}

Answer 1

When you are inserting, you are making a new BHeap object and then passing that to merge(). Your new BHeap has no rightSibling, so you skip the entire while loop and just return the new BHeap. So the new BHeap becomes the root of the whole BHeap and you throw out what was there before.

Update: I'm not going to write pseudo-code because it's right there in your code.

So you make a new BHeap and Insert(1). Your Insert method makes a second new BHeap and then checks the root of the current BHeap. That's null, so the second BHeap becomes the root. That's fine.

Now you Insert(2). Again, create another BHeap. This time the root of the current BHeap is not null so we call merge passing in the new BHeap. Note that this new BHeap is now referred (inside merge) as y. Also note that you have done nothing to this new BHeap aside from setting the key field so all other fields are null.

Inside merge you make yet another BHeap object, and make another reference currentHeap that refers to y. (Again, only the key field has been set so all other fields are null.) You refer to y's rightSibling as nextHeap and then comes the while loop. The while loop says that while the rightSibling of currentHeap is not null, do a bunch of stuff.

But as I've said above, everything about currentHeap (aka y aka the brand new BHeap you created in Insert) is null. So the entire while loop is skipped and you return y from merge.

Insert then accepts the return value from y and sets that as the root of the current BHeap. The old root is discarded and sits in the corner weeping bitterly at its sad fate before the garbage collector comes along and shuffles it into an early grave. The new root cheers triumphantly and reigns supreme, the king of the BHeap (and the only member of the BHeap)... until you call Insert(3).

And you? You learn how to use a debugger.

Answer 2

In your method merge you pass a BHeap object y. You do change anything as the BHeap object you have created and passed to merge in your insert method does not add any siblings. The while loop is never run.

Also, I think you may want to review your merge method. It seems you do not ever take into account the current BHeap that you are merging into and simply reformat the given BHeap argument.