Re: [Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #11151: Bug in update method for fibonacci heap.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-04-05 17:27:40

#11151: Bug in update method for fibonacci heap.
  Reporter: Søren Enevoldsen <senevo10@…> | Owner: timblechmann
      Type: Bugs | Status: new
 Milestone: To Be Determined | Component: heap
   Version: Boost 1.57.0 | Severity: Problem
Resolution: | Keywords:

Comment (by Søren Enevoldsen <senevo10@…>):

 I've been unable in several attempts to reproduce the problem. There needs
 to be a lot of boilerplate to get the indirect referencing of values, such
 that other values than the current (top()) can be changed.

 I have, however, found a possible related problem, that appears when
 entries "move past each other" in priority. In this case it is possible I
 did something wrong; maybe missed some requirement for elements? The
 following example have an array of numbers. I indirectly add increasing
 values (+5 each) to the heap. The highest value, also the "rightmost",
 gets picked first. Before removing it, I increase the value to the left
 and update the heap. I tested for 4 different scenarios:

 Use Update and increment by 5: Works correct.
 Use Increase and increment by 5: Works correct.
 Use Update and increment by 15: Correct sum. But wrong reason. The entries
 in the heap have been corrupted.
 Use Increase and increment by 15: Core dump!

 #include <iostream>
 #include <boost/heap/fibonacci_heap.hpp>
 #include <boost/heap/pairing_heap.hpp>

 using namespace boost::heap;

 struct EntryLocation;

 typedef fibonacci_heap<EntryLocation> HeapType;

 struct Entry
         int num;
         HeapType::handle_type handle;
         Entry() : num(0) {}
         Entry(int number) : num(number) {}
         bool operator<(const Entry& rhs) const {
                 return num < rhs.num;

 struct EntryLocation {
         int index;
         std::vector<Entry>* entries;
         EntryLocation() = delete;
         EntryLocation(int i, std::vector<Entry>* e) : index(i), entries(e)
         Entry& getEntry() const {
                 return entries->at(index);
         bool operator<(const EntryLocation& rhs) const {
                 return getEntry() < rhs.getEntry();

 int main(int argc, char const *argv[])
         int size = 5;
         auto heap = HeapType();
         std::vector<Entry> entries(size);

         //Create entries
         for (int i=0; i < size; i++) {
                 entries[i] = Entry(i * 10);
                 EntryLocation location(i, &entries);
                 auto handle = heap.push(location);
                 entries[i].handle = handle;

         //Do weird sum
         int sum = 0;
         while (!heap.empty()) {
                 auto& location =;
                 auto& entry = location.getEntry();
                 sum += entry.num;

                 std::cout << "Index: " << location.index << " has value: "
 << entry.num << std::endl;

                 //Modify entry to the "left"
                 if (location.index > 0) {
                         auto& leftEntry = entries[location.index - 1];
                         leftEntry.num += 5; // <<<<<<<< HERE. Try changing
 to 15.


         std::cout << sum << std::endl;
         return 0;

Ticket URL: <>
Boost C++ Libraries <>
Boost provides free peer-reviewed portable C++ source libraries.

This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:18 UTC