Heap.md 删除示例代码出错
作者: boulce创建于 2024年5月3日更新于 2024年5月3日
int delete_max_heap() { if (heapSize == 0) // return if the array is empty return 0;
int item = maxHeap[1]; // store the value of the root node
maxHeap[1] = maxHeap[heapSize]; // move the value of the last node to the root
maxHeap[heapSize--] = 0; // decrease the heap size by one and initialize the last node to 0
for (int i = 1; i * 2 <= heapSize;) {
// if the last node is greater than both the left node and the right node, stop
if (maxHeap[i] > maxHeap[i * 2] && maxHeap[i] > maxHeap[i * 2 + 1]) {
break;
}
// if the left node is greater than the right node, swap
else if (maxHeap[i * 2] > maxHeap[i * 2 + 1]) {
swap(i, i * 2);
i = i * 2;
}
// if the right node is greater than the left node
else {
swap(i, i * 2 + 1);
i = i * 2 + 1;
}
}
return item;} 似乎没有检查 "i2+1" 是否在 heapSize 范围内,因此这是一个问题。for 循环中只检查 i2 <= heapSize,因此当 i2 等于 heapSize 时,i2+1 将超出 heapSize,与无效的数组值进行比较。需要修改代码。
内容来源: gyoogle/tech-interview-for-developer