Member Avatar for brooklyn1991

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 :)

  • 2 Contributors
  • 1 Reply
  • 350 Views
  • 12 Years Discussion Span
  • Latest Post Latest Post by DGPickett

Dani AI

Generated

Diagnosis and targeted fixes for the “previous nodes disappear after insert” symptom (for )

The behavior described matches a classic bug in the merge stage: when building the merged root-list the tail pointer is never advanced. Each time the code sets P->sibling = <chosen node> but does not do P = P->sibling; immediately afterward, so the same P->sibling slot gets overwritten repeatedly and earlier nodes become unreachable. Adding that single advancement in both the main two-list loop and the “append remaining nodes” loops will restore a correct linked list of roots.

Other practical fixes and sanity checks

  • Ensure every newly-created singleton node used for insertion is fully initialized (parent, child, sibling, degree). Example:

    x->p = x->child = x->sibling = NULL;
x->degree = 0;

    Not initializing those pointers can produce exactly the loss/overwrite symptoms seen during subsequent merges.

  • Confirm unionBinomialHeap follows the CLRS pattern for max-heaps (your reversed comparison looks correct). Leave the next_x = x->sibling update at the end of the loop; if x or next_x is NULL the loop should exit cleanly.

Debugging checklist (short)

  • Print the merged root list immediately after mergeBinomialHeap and before unionBinomialHeap to verify all roots are present. For example:
    for (node *t = H->head; t; t = t->sibling)
printf("root %p key=%d deg=%d sib=%p child=%p\n", (void*)t, t->key, t->degree, (void*)t->sibling, (void*)t->child);
  • Run Valgrind or a memory checker for invalid reads/writes and to catch accidental overwrites or use-after-free.
  • Avoid returning a mix of newly allocated heap structures and old ones (your merge sometimes returns H1/H2 directly); that can cause leaks and confusing ownership semantics—either return a consistently allocated heap or document ownership clearly.

Note on alternatives: ’s idea of using an array of roots changes merge complexity and is valid for other optimizations, but for the pointer-based approach the missing P = P->sibling; and uninitialized node fields are the primary causes of the insertion problem.

Member Avatar for DGPickett

I optimized a Binomial min heap in c++, great for low costs when you discard the heap not empty because you have your spanning tree or shortest route. I changed the root to an array for fast merge.

#include <iostream>
#include <exception>
#include <sys/time.h>
#include <ctime>

using namespace std;

template <class T>
class fmin_tree {
	struct fmnode {
		fmnode * next, * child ;
		T value ;
	};

 private:
	fmnode ** root = nullptr ;
	size_t sz = 0L;
	char hmax = 0; // max degree of any tree

 public:
	fmin_tree(){
		root = new fmnode *[64];

		for ( int i = 0 ; i < 64 ; i++ ){
			root[i] = nullptr ;
		}
	}

	~fmin_tree(){
		delete[] root;
	}

	// insert into root sorted by height or merge with same, insert that
	void merges( fmnode * t, char h ){
		// hang input in root list
		while( root[h] ){ // occupied, need to merge
			fmnode *t2 ;

			// ensure t <= t2
			if ( root[h]->value > t->value ){
				t2 = root[h];
			} else {
				t2 = t ;
				t = root[h];
			}

			t2->next = t->child ;
			t->child = t2;
			root[h++] = nullptr ;
		} // end while true

		if ( h > hmax ){
			hmax = h ;
		}

		root[h] = t ;
// cerr << sz << " size merges\n"; dump();
	} // end merges()

	void push( T &t ){
		fmnode * tmp ;

		if ( !( tmp = new fmnode )){
			perror( "new fmnode" );
			exit( 1 );
		}
// cerr << tmp << " new node\n" ;

		tmp->value = t;
		tmp->child = tmp->next = nullptr ;
		sz++ ;
		merges( tmp, 0 );
	}

	struct pop_empty : std::exception {
		const char* what() const noexcept {
			return "pop of empty min heap\n";
		}
	};

	T pop(){
		if ( !sz ){
			pop_empty e;
			throw e;
		}

		sz-- ;
		short h = -1 ;
		T ret ;

		for ( int i = 0 ; i <= hmax ; i++ ){ // find min
			if ( root[i] ){
				if ( h < 0 || root[i]->value < ret ){
					h = i ;
					ret = root[i]->value ;
				}
			}
		}

		fmnode * c = root[h]->child ;
		delete root[h] ;
		root[h] = nullptr ;

		if ( h == hmax ){ // removing max degree tree
			hmax-- ;
		}

		while ( c ){ // install the children on root
			// children of h are h-1, h-2, etc.
			fmnode * c2 = c ;
			c = c->next ;
			c2->next = nullptr ;
			merges( c2, --h );
		}

		return ret ;
	}

	void clear(){
		for ( int i = 0 ; i <= hmax ; i++ ){
			clear( root[i] );
			root[i] = nullptr ;
		}

		sz = 0L ;
		hmax = 0 ;
	}

	void clear( fmnode *root ){
		if ( root ){
			for ( fmnode * t = root ; t ; ){
				clear( t->child );
				t = t->next ;
				delete root ;
// cerr << root << " delete clear\n" ;
				root = t;
			}
		}
	}

	bool isEmpty(){
		return !sz ;
	}

	size_t size(){ return sz ; }

	void dump(){
		for ( int i = 0 ; i <= hmax ; i++ ){
			dump( root[i], "" );
		}
	}

	void dump( fmnode * root, string pfix ){
		if ( ! root ){
			return ;
		}

		for ( fmnode * t = root ; t; t = t->next ){
			cout << pfix << t->value << endl ;
			dump( t->child, pfix + '\t' );
		}
	}

	int depth(){
		int ret = 0 ;

		for ( int i = 0 ; i <= hmax ; i++ ){
			int j = depth( root[i] );

			if ( j > ret ) ret = j ;
		}

		return ret ;
	}

	int depth( fmnode * root ){
		if ( ! root ) return 0 ;

		int d, dm = 0 ;

		for ( fmnode * t = root ; t; t = t->next ){
			if ( ( d = depth( t->child )) > dm ){
				dm = d ;
			}
		}

		return dm + 1 ;
	}

	float adepth(){
		unsigned long d = 0L;

		for ( int i = 0 ; i <= hmax ; i++ ){
			d += adepth( root[i], 1 );
		}

		return d * 1.0f / sz ;
	}

	unsigned long adepth( fmnode * root, int d ){
		if (!root) return 0L;

		unsigned long ret = d ;

		for ( fmnode * t = root ; t; t = t->next ){
			ret += adepth( t->child, d + 1 );
		}

		return ret ;
	}
};

int main(int argc, char ** argv){
	fmin_tree<int> tree;
	struct timeval time_now;
	int i, *randa;

	for ( int j = 3 ; j < 100000000 ; j = (j<<1) + 1 ){
		cout << "\nLoad " << j << endl ;
		if ( argc >  1 ){
			randa = new int[j];
			for ( i = 0 ; i < j ; i++ ){
				randa[i] = rand();
			}
		}
		
	    	gettimeofday(&time_now, nullptr);
	    	unsigned long msecs_start = time_now.tv_sec * 1000000 + time_now.tv_usec;
		for ( i = j-1 ; i >= 0 ; i -= 2 ){
			// cerr << "push even high\n" ;
			tree.push( argc > 1 ? randa[i] : i );
		}
		for ( i = 1 ; tree.size() < j ; i += 2 ){
			// cerr << "push odd low\n" ;
			tree.push( argc > 1 ? randa[i] : i );
		}
	    	gettimeofday(&time_now, nullptr);
	    	unsigned long msecs_end = time_now.tv_sec * 1000000 + time_now.tv_usec;
		cout << msecs_end - msecs_start << " microseconds\n" ;
		cout << "Depth " << tree.depth() << ", avg. depth " << tree.adepth() << ", size " << tree.size() << endl ;
		if ( tree.size() < 20 ){cout << "dump:\n"; tree.dump();}
		cout << "Pop half\n";
	    	gettimeofday(&time_now, nullptr);
	    	msecs_start = time_now.tv_sec * 1000000 + time_now.tv_usec;
		for ( i = 0 ; i < j>>1 ; i++ ) tree.pop();
	    	gettimeofday(&time_now, nullptr);
		if ( tree.size() < 10 ){cout << "dump:\n"; tree.dump();}
	    	msecs_end = time_now.tv_sec * 1000000 + time_now.tv_usec;
		cout << msecs_end - msecs_start << " microseconds\n" ;
		cout << "Depth " << tree.depth() << ", avg. depth " << tree.adepth() << ", size " << tree.size() << endl ;
		cout << "Load half" << endl ;
	    	gettimeofday(&time_now, nullptr);
	    	msecs_start = time_now.tv_sec * 1000000 + time_now.tv_usec;
		for ( i = 0 ; i < j>>1 ; i += 2 ){
			tree.push( argc > 1 ? randa[i] : i );
		}
		for ( i = (j>>1) - 2 ; tree.size() < j ; i -= 2 ){
			tree.push( argc > 1 ? randa[i] : i );
		}
	    	gettimeofday(&time_now, nullptr);
	    	msecs_end = time_now.tv_sec * 1000000 + time_now.tv_usec;
		cout << msecs_end - msecs_start << " microseconds\n" ;
		cout << "Depth " << tree.depth() << ", avg. depth " << tree.adepth() << ", size " << tree.size() << endl ;
		if ( tree.size() < 20 ){cout << "dump:\n"; tree.dump();}
		cout << "Clearing\n" ;
	    	gettimeofday(&time_now, nullptr);
	    	msecs_start = time_now.tv_sec * 1000000 + time_now.tv_usec;
		tree.clear();
	    	gettimeofday(&time_now, nullptr);
	    	msecs_end = time_now.tv_sec * 1000000 + time_now.tv_usec;
		cout << msecs_end - msecs_start << " microseconds\n" ;
		if ( argc > 1 ) delete[] randa ;
	}

	return 0;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.