Sanity checks fail on unstable binomial heap when pushing elements of same weight

[anonymous]

Hi, I have come across a bug according to which sanity checks fail on unstable binomial heaps when pushing elements of same weight. If sanity checks are not enabled, pushing/popping is done successfully, but in that case assertions in user code fail (I was just comparing the size of the heap with that of a counter that keeps track of the number of elements contained in the heap).

Furthermore, the result of empty() is not always aligned with that of size(), so for example empty() might report true, while size() might report 1. empty() gives always a correct result, since it just returns the result of the comparison `top_element == NULL', while size() reports the size of the size_holder, which seems that is not updated correctly. If the heap is defined as stable, there is no such problem.

Tested versions are 1.57.0 and 1.58.0 and are both affected. You may find the source code to reproduce such behavior in the attached .cpp file. There, I also include a fibonacci heap (apart from stable/unstable binomial heaps) in which the bug is not present.

Thanks, Babis

[anonymous]

File to reproduce the bug

[timblechmann]

thanks for the reproducer ... unfortunately i won't be able to have a closer look at this atm ... so it might take some time ...

[timblechmann]

fixed in develop