Opened 16 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)
Note: See
TracTickets for help on using
tickets.