#ifndef BMHNODE_S
	#define BMHNODE_S

	template<class T>
	struct bMHNode {
		bMHNode<T> * next, * child ;
		T value ;
		char rank ; // height / degree / rank / power
	};
#endif

template<class T>
class binomialMinHeap {
protected:
	bMHNode<T> * root = nullptr ;
	size_t sz = 0L ;

	// insert into root sorted by height or merge with same, insert that
	void merges( bMHNode<T> * t ){
		bMHNode<T> * t2 = root, * last = nullptr ;
		char rank = t->rank ;

		while( t2 ){ // walk down root
			char rank2 = t2->rank ;

			if ( rank2 < rank ){ // t high, check next
				last = t2 ;
				t2 = t2->next ;
				continue ;
			}

			if ( rank2 > rank ){ // t low, insert below
				break ; // done with this t
			}

			// t and t2 have same rank
			bMHNode<T> * t3 = t2->next ; // save next
			t2->next = nullptr ; // cut t2 out
			t = merge( t2, t ); // t goes down
			rank++ ;
			t2 = t3 ; // advance to next t2
		} // end while t2

		// found insert point
		t->next = t2 ;

		if ( last ) { // snap it in
			last->next = t ;
		} else {
			root = t ;
		}
	} // end merges()

	bMHNode<T> * merge( bMHNode<T> * t, bMHNode<T> * t2 ){ // merge trees
		char rank = 1 + ( t->rank > t2->rank ? t->rank : t2->rank ) ;

		if ( t->value < t2->value ){
			t2->next = t->child ;
			t->child = t2 ;
			t->rank = rank ;
			return t ;
		}

		t->next = t2->child ;
		t2->child = t ;
		t2->rank = rank ;
		return t2 ;
	} // end merge

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

	void clear( bMHNode<T> *root ){
		while ( root ){
			clear( root->child );
			bMHNode<T> * t = root->next ;
			delete root ;
			root = t ;
		}
	}

public:
	~binomialMinHeap(){ // destructor frees all
		clear();
	}

	void push( T &t ){
		sz++ ;
		bMHNode<T> * tmp ;

		if ( !( tmp = new bMHNode<T> )){
			perror( "new bMHNode<T>" );
			exit( 1 );
		}

		tmp->value = t ;
		tmp->child = tmp->next = nullptr ;
		tmp->rank = 0 ;
		merges( tmp );
	}

	T top(){ // used in pop to merge all
		if ( !sz ){
			pop_empty e ;
			throw e ;
		}

		bMHNode<T> * t = root->next ;
		root->next = nullptr ;

		while ( t ){ // merge all root into one tree
			bMHNode<T> * t2 = t->next ;
			t->next = nullptr ;
			root = merge( root, t );
			t = t2 ;
		}

		return root->value ;
	}

	T pop(){
		top(); // ensure one root tree
		sz-- ;
		bMHNode<T> * c = root->child ;
		delete root ;
		root = nullptr ;

		while ( c ){ // hang all children in root
			bMHNode<T> * c2 = c ;
			c = c->next ;
			c2->next = nullptr ;
			merges( c2 );
		}
	}

	size_t size(){
		return sz ;
	}

	void clear(){
		clear( root );
		root = nullptr ;
		sz = 0 ;
	}

	bool isEmpty(){ return ! sz ; }
}; // end binomialMaxHeap