IntervalHeap FindMin() gives incorrect result after a Replace() operation

sestoft / C5

C5 generic collection library for C#/.NET

http://www.itu.dk/research/c5/

MIT License

1.03k stars 181 forks source link

IntervalHeap FindMin() gives incorrect result after a Replace() operation #13

Closed endlessfalls closed 11 years ago

endlessfalls commented 11 years ago

After a certain (rather long) sequence of Add/Replace/DeleteMin operations, FindMin() will return an incorrect item (ie. there is a smaller value in the heap than the one returned). Additionally, Check() returns false, suggesting that the heap has been corrupted.

I am using revision: fc2109e99e2dfa748a2fe8bde4a94d2cb8918cd9 The sequence of operations which breaks it: https://dl.dropboxusercontent.com/u/9116381/BreakIntervalHeap.cs

sestoft commented 11 years ago

I'll look into this -- and have a theory about what's wrong but haven't yet had time to fix. / Peter

sestoft commented 11 years ago

I've identified and fixed the problem (in method heapifyMax on class IntervalTree), added unit test cases, and pushed the updated source as version a9b6fc0.

I hope Rasmus will do whatever is needed for additional packaging/prebuilt packages, continuing his excellent work in this direction.

Peter