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