C 语言实现大根堆：从原理到代码详解

思路解析：

• 必须检查 malloc 是否成功，避免空指针访问。
• 销毁后记得将指针置为 NULL，防止野指针。

2. 元素交换

堆化过程中经常需要交换父子节点的值。

void Swap(HeapDataType* child, HeapDataType* parent) {
    HeapDataType temp = *child;
    *child = *parent;
    *parent = temp;
}

3. 堆化操作

这是堆最核心的部分，分为向上调整和向下调整。

向上调整（Insert）

新元素插入到末尾后，如果破坏了堆性质，需要从下往上调整。

void AdjustUp(HeapDataType* arr, int child) {
    assert(arr);
    int parent = (child - 1) / 2;
    while (child > 0) {
        // 大根堆：子节点大于父节点则交换
        if (arr[child] > arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

注意点：

• 循环条件写成 child > 0 比 parent >= 0 更直观，因为当 child 为 0 时已到达堆顶。
• 时间复杂度为 O(logN)。

向下调整（Delete/Build）

删除堆顶元素或建堆时，通常从根节点开始向下调整。

void AdjustDown(HeapDataType* arr, int size, int parent) {
    assert(arr);
    assert(parent >= 0 && parent < size);
    
    int child = parent * 2 + 1;
    while (child < size) {
        // 找出左右孩子中较大的那个
        if (child + 1 < size && arr[child + 1] > arr[child]) {
            ++child;
        }
        
        // 如果父节点小于较大子节点，则交换
        if (arr[child] > arr[parent]) {
            Swap(&arr[parent], &arr[child]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

关键点：

• 总是先比较左右孩子，选出较大的一个再与父节点比较。
• 只有当父节点小于子节点时才交换，否则说明该位置已满足堆性质。

4. 插入与删除

插入元素

直接插入末尾，然后向上调整。

void HeapPush(Heap* pheap, HeapDataType data) {
    assert(pheap);
    
    // 扩容检查：二倍扩容策略
    if (pheap->size == pheap->capacity) {
        HeapDataType* newSpace = (HeapDataType*)realloc(
            pheap->base, sizeof(HeapDataType) * pheap->capacity * 2);
        if (newSpace == NULL) {
            perror("realloc failed\n");
            return;
        }
        pheap->base = newSpace;
        pheap->capacity *= 2;
    }
    
    pheap->base[pheap->size] = data;
    pheap->size++;
    
    // 插入后向上调整
    AdjustUp(pheap->base, pheap->size - 1);
}

删除元素

删除堆顶元素，将末尾元素移到堆顶，然后向下调整。

void HeapPop(Heap* pheap) {
    assert(pheap && pheap->size > 0);
    
    // 交换堆顶和堆尾
    Swap(&pheap->base[0], &pheap->base[pheap->size - 1]);
    pheap->size--;
    
    // 非空时继续向下调整
    if (pheap->size > 0) {
        AdjustDown(pheap->base, pheap->size, 0);
    }
}

为什么这样删？ 直接删除堆顶会导致后续元素前移，破坏完全二叉树结构。通过交换堆尾元素到堆顶，能最大程度保持结构完整性，只需一次向下调整即可恢复堆性质。

5. 辅助函数

bool HeapEmpty(Heap* pheap) {
    assert(pheap);
    return pheap->size == 0;
}

HeapDataType HeapTop(Heap* pheap) {
    assert(pheap);
    assert(pheap->base);
    return pheap->base[0];
}

int HeapSize(Heap* pheap) {
    assert(pheap);
    return pheap->size;
}

总结

实现堆的关键在于理解完全二叉树的数组存储特性。插入时利用向上调整维护性质，删除时利用向下调整。动态扩容保证了灵活性，断言检查确保了安全性。掌握这些逻辑后，无论是构建优先队列还是实现堆排序，都能游刃有余。