Hello, everyone!:) I am new to Daniweb and I would like a little help in implementing Binomial Heap subroutines in C, especially insertion in Heap. For my application it is necessary to implement max-heaps(i.e., roots storing the maximum value) in stead of min-heaps(i.e., root storing minimum value) in ANSI C. I have written a few subroutines - but things are not working properly. I will explain my codes here with code snippet and my problem.
struct _tnode{
int key;//a field key for its key
int degree;/*a field degree for the number of children -or for the degree of the tree rooted at the node*/
int u; //to store the no. of entry in the graphic sequence
struct _tnode *child;//a pointer child , which points to the leftmost-child
struct _tnode *sibling;//a pointer sibling, which points to the right-sibling
struct _tnode *p;//a pointer p, which points to the parent
};
typedef struct _tnode node;
struct _theap{
node *head;//only a pointer to point to a node, next nodes would be the siblings
};
typedef struct _theap heap;this was the definition of Tree nodes and heap structure. the field "degree" stores the degree of the binomial tree rooted at current node, "key" stores the value, "u" is satelite data.
I used initializeHeap() to initiate a Heap using malloc with the head pointer being NULL. Now there are some subroutines like binomialHeapFindMaximum(heap *H) which returns pointer to a root node in the heap which has the maximum key value. Now there is mergeBinomialHeap() which merges two binomial heaps H1 and H2 such that trees of same degree(s) fall next to each other. Obviously, the heap structure, returned by mergeBinomialHeap is modified by the calling subroutine unionBinomialHeap() which uses the previous routine, modifies the returned Heap and returns a proper heap structure. There is one more helper subroutine binomialTreeLink() that takes two root nodes of two trees of same degree as input, makes the first one second tree's left subtree. I am providing codes for these three subroutines here.
//this function blindly merges two binomial heaps into one binomial heap, with placing trees of same degrees next to each other
//this is more like the "MERGE" subroutine in MergeSort//
//it is a helper subroutine to the union subroutine - the heap returned is not a
//proper binomial heap.
heap* mergeBinomialHeap(heap* H1, heap* H2){
heap* H = initializeHeap();//new heap initialized to hold the merged H1 & H2
node* P= H->head ;
node* P1 ;
node* P2 ;
P1 = H1->head;
P2 = H2->head;
//if both are empty heaps, return empty heap.
if((P1==NULL) && (P2==NULL)){
return H;
}
//if one of them is empty heap, return the other
if(((P1==NULL) && (P2!=NULL))||((P1!=NULL) && (P2==NULL))){
if(P1==NULL) return H2;
else return H1;
}
//if none of them is empty heap, merge properly and return
if((P1->degree)<(P2->degree)){
P=P1;
P1=P1->sibling;
}
else{
P=P2;
P2= P2->sibling;
}
H->head = P; /*after first node chosen by P from P1 and P2, make H->head point to it*/
//now fill up the rest of the new heap
while((P1!=NULL) && (P2!=NULL)){
if((P1->degree)<(P2->degree)){
P->sibling = P1;
P1=P1->sibling;
}
else{
P->sibling = P2;
P2=P2->sibling;
}
}
//one of P1 or P2 is NULL, so fill the trees from other heap
if(P1==NULL){
while(P2!=NULL){
P->sibling = P2;
P2 = P2->sibling;
}
}
if(P2==NULL){
while(P1!=NULL){
P->sibling = P1;
P1=P1->sibling;
}
}
//end the new heap properly
P->sibling = NULL;
//printf("Binomial heaps merged\n");
return H;
}
/*this function merges two heaps using mergeBinomialHeap() and modifies it to a proper binomial heap*/
heap* unionBinomialHeap(heap* H1, heap* H2){
heap* H =initializeHeap();
H = mergeBinomialHeap(H1,H2);
if(H->head== NULL)
return H;
//printf("H not empty\n");
node* prev_x = NULL;
node* x = H->head;
node *next_x = x->sibling;
while(next_x !=NULL){
if((x->degree != next_x->degree) || (next_x->sibling != NULL && (next_x->sibling)->degree == x->degree)){
prev_x = x;//case 1 and 2
x= next_x;
}
else if(x->key >= next_x->key){//this inequality sign is revered, as it is max-heap
x->sibling = next_x->sibling;//case 3
binomialTreeLink(next_x, x);
}
else {
if(prev_x== NULL){
H->head = next_x;
}
else{
prev_x->sibling = next_x;
}
binomialTreeLink(x,next_x);
x= next_x;
}
next_x = x->sibling;//this operation is needed for all cases - so done at the end of the loop
}
//printf("union binomial heap done\n");
return H;
}
//calling function should check y->key < z->key, because this function makes z the //parent of new tree
void binomialTreeLink(node* y, node* z){//used to merge two binomial trees of same order
y->p = z; //two root nodes are passed by pointers
y->sibling = z->child;
z->child = y;
z->degree +=1;
}When I am trying to use these subroutines from some calling functions, the problem, after a lots of debugging attempt, seems to me is that whenever I am using these subroutines to insert a new node in a heap - the previous nodes are getting deleted!! The insertNode subroutine is as follows:
//Inserts a node into the heap
//make a binomial heap with a tree of degree 0 with the node and
//merge it with the Heap we need to insert the node in
heap* binomialHeapInsert(heap* H, node* x){
heap* h = initializeHeap();
h->head = x;
//printf("inside binomial heapInsert\n");
//merge the single node with the heap
H = unionBinomialHeap(H,h);
return H;
}the calling subroutine which uses insertNode, first defines a Node pointer x, allocate space for it, makes proper modifications to its fields - finally calls this insertNode subroutine and tries to insert it. Now, as I have already said, something is deleting the previous nodes from the heap H and keeping only the current node being inserted. :( My guess is binomialTreeLink function is not working properly. Can anyone point out any mistake in these function? Any help would be greatly appreciated. Thanks in advance :)
