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