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: 151
java
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