id	summary	reporter	owner	description	type	status	milestone	component	version	severity	resolution	keywords	cc
13087	Boost::binomial_heap Merge error	jun.kudo@…	timblechmann	"Configured with BOOST_HEAP_SANITYCHECKS turned on.
Binomial heap hits an assertion failure during the second merge routine in the attached example.


{{{
#include ""boost/heap/binomial_heap.hpp""
typedef boost::heap::binomial_heap<int> Heap;

int main(int argc, char* argv[]) {
  Heap heap0;
  size_t heap0_size = 13;
  size_t max_range = 100;
  for (size_t ix = 0; ix < heap0_size; ++ix) {
    heap0.push(rand() % max_range);
  }

  Heap heap1; 
  size_t heap1_size = 5;
  for (size_t ix = 0; ix < heap1_size; ++ix) {
    heap1.push(rand() % max_range);
  }
  heap0.merge(heap1);
  
  Heap heap2; 
  size_t heap2_size = 1;
  for (size_t ix = 0; ix < heap2_size; ++ix) {
    heap2.push(rand() % max_range);
  } 
  heap2.merge(heap0);

}
}}}

When heap1 is merged into heap0, the underlying forest incorrectly contains two 2-degree trees.  This error is later caught in a sanity assertion check when heap0 is merged into heap2.

I believe the error stems the case identified by line 668 in binomial_heap.hpp.  When the two root degrees are equal and a carry tree with degree less than both exist, the carry tree is inserted into trees.  However, after this insertion, the this_iterator is incorrectly iterated forward which causes the algorithm to behave incorrectly.  In the case provided above, this causes the merge algorithm to skip the degree-2 / degree-2 merge between this and rhs, and instead causes rhs's degree-2 tree to be simple inserted into trees.
"	Bugs	new	To Be Determined	heap	Boost 1.64.0	Problem