数据结构：二叉树与堆的实现详解

堆的概念与结构

堆的定义

如果有—个关键码的集合 K = {k0, k1, k2, ... , kn}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki <= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2)，i = 0、1、2...，则称为小堆 (或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

简单来说：大根堆的根节点值最大，小根堆的根节点值最小。堆中某个结点的值总是不大于或不小于其父结点的值；堆总是一棵完全二叉树。

性质：对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从 0 开始编号，则对于序号为 i 的结点有：

• 若 i > 0，i 的位置结点的双亲序号：(i - 1) / 2；i = 0，i 为根结点编号，无双亲结点。
• 若 2i + 1 < n，左孩子序号：2i + 1，2i + 1 >= n，则无左孩子。
• 若 2i + 2 < n，右孩子序号：2i + 2，2i + 2 >= n，则无右孩子。

堆的实现代码

堆底层结构为数组，因此定义堆的结构也与顺序表相同。操作方面，也与顺序表相同，不同点是，堆是有大根堆、小根堆的结构要求的，所以实现时也不是那么容易。

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int type;

typedef struct Heap {
    type* a;
    int size;
    int capacity;
}HP;

void HPInit(HP* h);
void HPDestroy(HP* h);
void HPPush(HP* h, type x);
void AdjustUp(type* a, int child);
void swap(int* a, int* b);
void HPPrint(HP* h);

1. 堆的初始化

堆的初始化是创建一个空堆并设置其初始容量、指针等基本属性的过程。本次实现选取大顶堆为例。

void HPInit(HP* h) {
    assert(h);
    h->a = NULL;
    h->capacity = h->size = 0;
}

由于堆的底层是顺序表，所以初始化的实现与顺序表的实现基本一致。

2. 堆的销毁

堆的销毁函数核心目标是释放动态分配的内存，避免内存泄漏，并将堆重置为空状态。

void HPDestroy(HP* h) {
    assert(h);
    if (h->a) {
        free(h->a);
    }
    h->capacity = h->size = 0;
}

3. 堆的插入数据

堆的插入，是有大根堆、小根堆要求的，所以每当我们插入一个值时，都要进行堆调整。需遵循'先插入元素，再向上调整'的核心逻辑。

在每次插入之前，我们认为是符合该（大根堆或小根堆）结构的状态，插入的值如果使树不符合该结构，则需让新插入的元素'上浮'到正确位置，恢复堆的性质。

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void AdjustUp(type* a, int child) {
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[parent] < a[child]) {
            swap(&a[parent], &a[child]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

void HPPush(HP* h, type x) {
    assert(h);
    // 扩容逻辑
    if (h->capacity == h->size) {
        int n = h->capacity == 0 ? 4 : 2 * h->capacity;
        type* tmp = (type*)realloc(h->a, n * sizeof(type));
        if (tmp == NULL) {
            perror("realloc failed");
            return;
        }
        h->a = tmp;
        h->capacity = n;
    }
    // 插入并调整
    h->a[h->size++] = x;
    AdjustUp(h->a, h->size - 1);
}

这里包含 swap（交换）、AdjustUp（向上调整）和 HPPush（堆插入）三个函数，核心是通过'扩容→插入→调整'维持堆的性质（以大顶堆为例）。

4. 堆打印值

堆打印值实际上与顺序表的值的打印一样，只是结果是按照堆的值的顺序。

void HPPrint(HP* h) {
    assert(h);
    int i;
    for (i = 0; i < h->size; i++) {
        printf("%d ", h->a[i]);
    }
    printf("\n");
}

测试示例

为了验证上述代码的正确性，我们可以编写一个简单的测试用例：

void test() {
    HP h;
    HPInit(&h);
    HPPush(&h, 10);   // 堆：10
    HPPush(&h, 20);   // 堆：20 10
    HPPush(&h, 6);    // 堆：20 10 6
    HPPrint(&h);
    HPPush(&h, 30);   // 堆：30 20 6 10
    HPPrint(&h);
    HPPush(&h, 60);   // 堆：60 30 6 10 20
    HPPrint(&h);
    HPDestroy(&h);
}

int main() {
    test();
    return 0;
}

运行结果会显示堆顶元素始终最大，符合大根堆的特性。