id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	revision
646	Bug in binomial heap with ties	Peter Madarasi	Alpar Juttner	"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 [https://lemon.cs.elte.hu/trac/lemon/browser/lemon/lemon/binomial_heap.h#L177 line 177 of binomial_heap.h] with
{{{
_min=findMin();
}}}
"	defect	new	major	LEMON 1.4 release	core	hg main