Hi all,

I’m observing a weird phenomenon when iterating over a binomial heap after pushing two values with the same priority.  Instead of printing the expected values twice, the ordered iterator seems to print three values.  I do not observe this behavior when using a Fibonacci heap or a binary heap.  I’ve attached sample code that demonstrates this behavior.  Can anyone help explain what’s going on?

Boost Version : Boost 1.64

Compiler : GCC 5.3.0

#include <iostream>

#include "boost/heap/fibonacci_heap.hpp"

#include "boost/heap/binomial_heap.hpp"

#include "boost/heap/d_ary_heap.hpp"

template <class HeapType>

void PrintHeap(HeapType const & heap) {

  std::cout << "Printing out heap : ";

  for (auto it = heap.begin(); it != heap.end(); ++it) {

    std::cout << *it << " ";

  }

  std::cout << "\n Printing out heap in order : ";

  for (auto it = heap.ordered_begin(); it != heap.ordered_end(); ++it) {

    std::cout << *it << " ";

  }

  std::cout << "\n\n";

}

int main(int /* argc */, char** /* argv */) {

  typedef boost::heap::binomial_heap<int> BinomialHeap;

  BinomialHeap binomial_heap;

  binomial_heap.push(1);

  binomial_heap.push(1);

  // Prints {1,1} and {1,1,1}

  PrintHeap(binomial_heap);

  typedef boost::heap::fibonacci_heap<int> FibonacciHeap;

  FibonacciHeap fibonacci_heap;

  fibonacci_heap.push(1);

  fibonacci_heap.push(1);

  // Prints {1,1} and {1,1}

  PrintHeap(fibonacci_heap);

  typedef boost::heap::d_ary_heap<int, boost::heap::arity<2>, boost::heap::mutable_<true>> BinaryHeap;

  BinaryHeap binary_heap;

  binary_heap.push(1);

  binary_heap.push(1);

  // Prints {1,1} and {1,1}

  PrintHeap(binary_heap);

}

Thanks!

Jun