Bug in binomial heap with ties

[Peter Madarasi]

In the current implementation, it may happen that the top-priority item (i.e. _min) is not a root of the heap. This happens because when we merge the minimum-priority item (_min) tree with an other tree whose root has the same priority, we do not make sure that the new root will be _min. This causes a lot of problems, because we may try to pop a non-root item.

The following code snippet demonstrates the issue.

ListDigraph g;
ListDigraph::Node v0 = g.addNode();
ListDigraph::Node v1 = g.addNode();
ListDigraph::NodeMap<int> ref(g,-1);
lemon::BinomialHeap<int,ListDigraph::NodeMap<int> > h(ref);
h.push(v0,0);
h.push(v1,0);
h.pop();
h.pop();

Before the pops, the heap consists of a single tree with root v1 and its only child is v0. However, the top priority item in the current implementation is v0, which is not a root in the heap! This causes an infinite loop in BinomialHeap::unlace.

One possible fix of this issue is to replace ​line 177 of binomial_heap.h with

_min=findMin();

[Alpar Juttner]

Thanks for the patch.

It would be nice to add a related test code to heap_test.cc

[Peter Madarasi]

Replying to Alpar Juttner:

Thanks for the patch.

It would be nice to add a related test code to heap_test.cc

The revised patch adds a new test case to heap_test.cc.