I'm implementing binary heap in golang. Given below is downheap function:
func (bh *BinaryHeap[V]) downheap(nodeIndex int) {
for nodeIndex <= bh.length {
priorIndex := nodeIndex
leftIndex := nodeIndex << 1
rightIndex := (nodeIndex << 1) + 1
if leftIndex <= bh.length && bh.priorityFunc(bh.nodes[leftIndex].GetValue(), bh.nodes[priorIndex].GetValue()) {
priorIndex = leftIndex
}
if rightIndex <= bh.length && bh.priorityFunc(bh.nodes[rightIndex].GetValue(), bh.nodes[priorIndex].GetValue()) {
priorIndex = rightIndex
}
...
While calculating leftIndex or rightIndex in above code, there is a potential cause of overflow (or negative value which makes program crash) if the number of elements in heap is close to math.MaxInt value (similar to recent bug in Java's Arrays.BinarySearch function)
- In case of 64-bit architecture: as int is equivalent to int64, I assume above implementation is practical.
- To support in 32-bit architecture: I have changed implementation as below due to potential cause of overflow error
func (bh *BinaryHeap[V]) downheap(nodeIndex int) {
for nodeIndex <= bh.length {
priorIndex := nodeIndex
leftIndex := int64(nodeIndex) << 1
rightIndex := (int64(nodeIndex) << 1) + 1
if leftIndex <= int64(bh.length) && bh.priorityFunc(bh.nodes[leftIndex].GetValue(), bh.nodes[priorIndex].GetValue()) {
priorIndex = int(leftIndex)
}
if rightIndex <= int64(bh.length) && bh.priorityFunc(bh.nodes[rightIndex].GetValue(), bh.nodes[priorIndex].GetValue()) {
priorIndex = int(rightIndex)
}
...
So, Is above implementation an ideal way to avoid the potential overflow error?