Open antevir opened 8 years ago
The BinaryHeap consistency can break if an item is removed under specific conditions. The bug can be reproduced with the code below:
#include "core-util/BinaryHeap.h" using mbed::util::BinaryHeap; using mbed::util::MinCompare; BinaryHeap<int, MinCompare<int>> heap; void testHeap() { UAllocTraits_t traits = { 0 }; int values[] = { 59, 46, 79, 7, 62, 6, 8, 10, 36, 11, 14, 70, 61, 1 }; heap.init(20, 20, traits); for (int i = 0; i < sizeof(values) / sizeof(int); i++) { heap.insert(values[i]); } heap.remove(11); while (!heap.is_empty()) { printf("%d ", heap.pop_root()); } }
The above code should print out all the values in rising order, i.e. the expected output is:
1 6 7 8 10 14 36 46 59 61 62 70 79
However, the actual output is:
1 6 7 10 8 14 36 46 59 61 62 70 79
It looks like the algorithm in remove() is not correct
remove()
ARM Internal Ref: IOTSFW-2788
The BinaryHeap consistency can break if an item is removed under specific conditions. The bug can be reproduced with the code below:
The above code should print out all the values in rising order, i.e. the expected output is:
However, the actual output is:
It looks like the algorithm in
remove()
is not correct