为何我实现的向下Heapify操作会将值替换为0，还存在其他潜在问题？

核心问题点 #

• 子节点越界判断逻辑错误
  堆数组有效下标范围是[0, fullness - 1]，但你在heapifyLookDown里判断子节点越界的条件是getChild1(element) > fullness，应该改为>= fullness。比如当fullness=7时，下标最大为6，若计算出的子节点下标为7就已经越界，原判断会允许访问heap[7]，读取到数组外的随机值（也就是你遇到的0），导致数值被错误替换。
• 向下堆化的递归逻辑错误
  你在完成父节点和子节点的交换后，同时递归处理左右两个子节点是多余的，仅需要递归处理被交换过的那个子节点即可，另一个子节点的堆性质没有被本次交换破坏，无需递归处理，否则会引发不必要的逻辑混乱。
• getParent函数实现冗余且存在浮点精度隐患
  无需用浮点运算计算父节点下标，直接使用整数运算return (element - 1) / 2即可，C语言整数除法自动向下取整，结果完全符合需求，还能避免浮点运算可能带来的精度误差。
• 批量初始化后建堆逻辑不完整
  建堆的正确做法是从最后一个非叶子节点开始倒序遍历执行向下堆化，仅从根节点执行一次向下堆化无法保证整个堆的性质正确。

修正后核心代码片段 #

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define SIZE 7

int heap[SIZE];
int fullness = 0;

// 修正后的getParent函数
int getParent(int element){
    return (element - 1) / 2;
}

int getChild1(int element){
    return element * 2 + 1;
}

int getChild2(int element){
    return element * 2 + 2;
}

// 重构后的向下堆化函数，逻辑更简洁可靠
void heapifyLookDown(int element){
    int left = getChild1(element);
    int right = getChild2(element);
    int smallest = element;

    // 正确判断左子节点是否在有效范围内
    if(left < fullness && heap[left] < heap[smallest]){
        smallest = left;
    }
    // 正确判断右子节点是否在有效范围内
    if(right < fullness && heap[right] < heap[smallest]){
        smallest = right;
    }

    if(smallest != element){
        // 交换当前节点和最小的子节点
        int temp = heap[element];
        heap[element] = heap[smallest];
        heap[smallest] = temp;
        // 仅递归处理被交换的子节点
        heapifyLookDown(smallest);
    }
}

// 原有向上堆化、插入等逻辑可保留使用
void minHeapifyLookUp(int element){
    if(element == 0){
        return;
    }
    int parent = getParent(element);
    if(heap[element] < heap[parent]){
        int temp = heap[element];
        heap[element] = heap[parent];
        heap[parent] = temp;
        minHeapifyLookUp(parent);
    }
}

void insertToHeap(int insert){
    heap[fullness] = insert;
    fullness++;
    minHeapifyLookUp(fullness-1);
}

int main()
{
    int numList[SIZE] = {400,-1,3,63,12,5,100};
    for(int i = 0; i < SIZE; i++){
        heap[i] = numList[i];
        fullness++;
    }
    // 从最后一个非叶子节点开始倒序遍历堆化，完成建堆
    for(int i = getParent(fullness - 1); i >= 0; i--){
        heapifyLookDown(i);
    }
    for(int i = 0; i < fullness; i++){
        printf("%d ", heap[i]);
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Eric