id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc	revision
681	Bug in radix heap	Peter Madarasi	Alpar Juttner	"Levente Birszki reports that the implementation of radix heap does not work
correctly in certain cases. It seems to mess up the sizes of the buckets, and it
may pop an item with non-minimal key. For example,

{{{
const int n = 10; // max num items
const int c = 10; // max key

lemon::RangeMap<int> map(n, -1);
lemon::RadixHeap<lemon::RangeMap<int>> heap(map, 0, c);

heap.push(0, 2); // (index, priority)
heap.push(1, 3);
heap.push(2, 4);

heap.pop(); // ok, pops (0, 2)
heap.increase(1, 5);
heap.pop(); // oops, pops (1, 5) instead of (2,4)
}}}

Attached is a possible fix of the issue. The patch also extends
[[source:test/heap_test.cc|heap_test.cc]] with the problematic example given
above. The solution is based on a proposal of Levente."	defect	new	major	LEMON 1.4 release	core	hg main