COIN-OR::LEMON - Graph Library

Opened 9 months ago

#681 new defect

Bug in radix heap

Reported by: Peter Madarasi Owned by: Alpar Juttner
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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 heap_test.cc with the problematic example given above. The solution is based on a proposal of Levente.

Attachments (1)

radixHeapFix.tar.gz (2.9 KB) - added by Peter Madarasi 9 months ago.

Download all attachments as: .zip

Change History (1)

Changed 9 months ago by Peter Madarasi

Attachment: radixHeapFix.tar.gz added
Note: See TracTickets for help on using tickets.