[Boost-bugs] [Boost C++ Libraries] #11394: Sanity checks fail on unstable binomial heap when pushing elements of same weight

Subject: [Boost-bugs] [Boost C++ Libraries] #11394: Sanity checks fail on unstable binomial heap when pushing elements of same weight
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-06-11 09:49:05

#11394: Sanity checks fail on unstable binomial heap when pushing elements of same
weight
-------------------------------------------------+-------------------------
 Reporter:  anonymous                            |      Owner:
     Type:  Bugs                                 |  timblechmann
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost 1.57.0                         |  Component:  heap
 Keywords:  binomial heap, unstable, sanity      |   Severity:  Problem
  checks, fail                                   |
-------------------------------------------------+-------------------------
 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

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/11394>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.