Priority Queue is Broken

[laskdaf]

I was testing the PQ recently, and noticed that when the PQ is emptied, the minimum value will now become 0 and will always be zero. This issue is that delete heapList[currentSize]; only sets the value at that index to null (0 in the case of uint256).

Let's say you have a PQ initially with 5 items. Then all items are removed. The length of the list is still 5. So if you call insert on the empty PQ, the item is inserted at index 5, not index 1. When percUp(1) is called, the item is still stuck at the end.

The easy solution to this is to add the line heapList.length = heapList.length.sub(1); at the end of delMin() function.

• Blockchain @ Berkeley Researcher

[smartcontracts]

@laskdaf Thanks for the detailed report. I submitted PR #105 fixing this issue and added unit tests to cover this case + others.