Unexpected behavior of ordered iteration of previously merged fibonacci heap

[mbradle@…]

Hello,

In some cases, if I merge fibonacci heap h1 into fibonacci heap h2, then merge heap h3 into h1, I get unexpected behavior if I then try to iterate h1 in order. If I clear h1 before merging in h3, I get the expected behavior. I get the expected behavior for the other mergeable heaps (binomial, pairing, skew).

The attached test_heap.cpp shows an example and test_heap_output.txt shows the output from execution on a linux computer. The heaps are sorted with minimum element at the top. The output of the fibonacci heap test (without clearing) is 1 3 4 5 instead of the expected 3 4 5. Other heaps give 3 4 5. Thanks, and best wishes.

Brad Meyer

[mbradle@…]

test code

[mbradle@…]

Output from execution of test code

[timblechmann]

fixed in git 916344f831e49dfd85854c5678b338524f5e61d2