[Boost-users] [Boost.Heap] Possible bug with ordered iterator and boost::heap::binomial_heap

Subject: [Boost-users] [Boost.Heap] Possible bug with ordered iterator and boost::heap::binomial_heap
From: Kudo, Jun (jun.kudo_at_[hidden])
Date: 2017-06-08 20:02:38

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