数据结构：二叉树进阶——堆的实现与原理

初始化时分配 NULL 并置零：

void Init_Heap(Heap* pHeap) {
    pHeap->arr = NULL;
    pHeap->size = pHeap->length = 0;
}

4.3.2 入堆（插入）

插入操作需遵循完全二叉树的特性，新元素只能追加到数组末尾。插入后可能破坏堆序性，因此需要向上调整。

向上调整算法思路： 将新节点与其父节点比较，若不符合堆序（如大根堆中子节点大于父节点），则交换位置，继续向上直至满足条件。

// 向上调整（大顶堆）
void adjustUP(Elemtype* arr, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (*(arr + parent) < *(arr + child)) {
            Swap(arr + parent, arr + child);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

// 堆插入
void Push_Heap(Heap* pHeap, Elemtype data) {
    // 扩容逻辑
    if (pHeap->size == pHeap->length) {
        int newLength = pHeap->length == 0 ? 4 : 2 * pHeap->length;
        Elemtype* newbase = (Elemtype*)realloc(pHeap->arr, newLength * sizeof(Elemtype));
        if (!newbase) {
            perror("内存申请失败");
            return;
        }
        pHeap->arr = newbase;
        pHeap->length = newLength;
    }
    // 插入并调整
    pHeap->arr[pHeap->size] = data;
    adjustUP(pHeap->arr, pHeap->size);
    pHeap->size++;
}

4.3.3 出堆（删除）

堆的删除通常针对堆顶元素（最值）。直接删除会破坏结构，标准做法是将堆尾元素移至堆顶，再向下调整。

向下调整算法思路： 比较父节点与左右子节点，若父节点小于较大子节点（大根堆），则交换，并继续向下，直到满足堆序。

// 交换函数
void Swap(Elemtype* a, Elemtype* b) {
    Elemtype temp = *a;
    *a = *b;
    *b = temp;
}

// 向下调整（大顶堆）
void adjustDown(Elemtype* arr, int size, int parent) {
    assert(arr);
    int child = parent * 2 + 1;
    while (child < size) {
        // 找出较大的子节点
        if (child + 1 < size && *(arr + child) < *(arr + child + 1)) {
            child++;
        }
        // 父节点与较大子节点比较
        if (*(arr + parent) < *(arr + child)) {
            Swap(arr + parent, arr + child);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 堆删除
void Pop_Heap(Heap* pHeap) {
    assert(!isEmpty(pHeap));
    // 堆顶与堆尾交换
    Swap(pHeap->arr, pHeap->arr + pHeap->size - 1);
    pHeap->size--;
    // 向下调整恢复堆序
    adjustDown(pHeap->arr, pHeap->size, 0);
}

4.3.4 辅助操作

判空只需检查 size 是否为 0；取最值直接返回数组首元素；销毁需释放内存并重置状态。

bool isEmpty(Heap* pHeap) {
    assert(pHeap);
    return pHeap->size == 0;
}

Elemtype Top_Heap(Heap* pHeap) {
    return pHeap->arr[0];
}

void Destory_Heap(Heap* pHeap) {
    free(pHeap->arr);
    pHeap->arr = NULL;
    pHeap->size = pHeap->length = 0;
}

4.4 完整示例代码

以下是一个完整的堆实现框架，支持大小顶堆切换：

// 小顶堆调整略作修改即可，此处省略重复代码
// 主函数演示
int main() {
    Heap Hp;
    Heap* pHeap = &Hp;
    Init_Heap(pHeap);

    // 模拟插入
    for (int i = 0; i < 5; i++) {
        Push_Heap(pHeap, i * 10);
    }

    // 查看堆顶
    printf("Top: %d\n", Top_Heap(pHeap));

    // 删除堆顶
    Pop_Heap(pHeap);
    printf("New Top: %d\n", Top_Heap(pHeap));

    Destory_Heap(pHeap);
    return 0;
}

五、总结

堆作为完全二叉树的顺序存储实现，利用数组下标规律高效维护父子关系。通过向上调整和向下调整算法，我们可以在 O(log n) 时间内完成插入和删除操作。掌握堆的原理，不仅有助于理解优先队列，也是学习排序算法（如堆排序）的基础。