数据结构堆详解：核心特性、实现与应用

// 堆的销毁
void HeapDestroy(heap* php) {
    assert(php);
    free(php->a);
    php->a = NULL;
    php->capacity = php->size = 0;
}

4. 堆的插入（含向上调整算法）

入堆的操作逻辑很简单：先把新数据直接插入到堆的末尾（对应数组的最后一个位置），插入后如果堆的结构不符合小根堆/大根堆的规则，就通过向上调整算法，把这个新元素逐步'往上挪'，直到它处于一个能让整个堆重新满足规则的位置。

// 入堆
void HeapPush(heap* php, HpDataType x) {
    assert(php);
    // 扩容
    if (php->capacity == php->size) {
        HpDataType* tmp = (HpDataType*)realloc(php->a, sizeof(HpDataType) * php->capacity * 2);
        if (tmp == NULL) {
            perror("realloc");
            return;
        }
        php->a = tmp;
        php->capacity = 2 * php->capacity;
    }
    php->a[php->size] = x;
    php->size++;
    // 向上调整
    AdjustUp(php->a, php->size - 1);
}

【向上调整算法】：

// 交换算法
void swap(HpDataType* p1, HpDataType* p2) {
    HpDataType x = *p1;
    *p1 = *p2;
    *p2 = x;
}

// 向上调整
void AdjustUp(HpDataType* a, int child) {
    // 计算父节点的索引
    int parent = (child - 1) / 2;
    // 循环条件：child > 0 表示当前节点还没到堆顶（堆顶节点的 child 为 0，无父节点）
    // 只要没到堆顶，就持续检查当前节点与父节点是否符合堆的规则
    while (child > 0) {
        // 孩子小于父亲就交换值
        if (a[child] < a[parent]) {
            swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

这段向上调整算法是针对小根堆设计的；如果要适配大根堆，只需要把判断条件改成'子节点值大于父节点'即可。

5. 堆的删除（含向下调整算法）

堆的删除操作是针对堆顶元素的，具体逻辑是：先把堆顶元素和堆的最后一个元素交换位置，接着删除数组末尾（原堆顶元素），最后对新的堆顶元素执行向下调整算法，让堆重新满足规则。

之所以不直接删除堆顶元素，是因为堆顶是堆的核心节点，直接删除会彻底打乱整个堆的父子节点逻辑，后续几乎无法恢复成合法的堆结构。

// 出堆
void HeapPop(heap* php) {
    assert(php);
    assert(!HeapEmpty(php));
    // 删除数据
    swap(&php->a[0], &php->a[php->size - 1]);
    php->size--;
    // 向下调整
    AdjustDown(php->a, php->size, 0);
}

【向下调整算法】:

// 交换算法
void swap(HpDataType* p1, HpDataType* p2) {
    HpDataType x = *p1;
    *p1 = *p2;
    *p2 = x;
}

// 向下调整
void AdjustDown(HpDataType* a, int n, int parent) {
    int child = 2 * parent + 1; // 假设左孩子小
    while (child < n) {
        // 选出孩子中小的那一个
        if (child + 1 < n && a[child + 1] < a[child]) { // 避免越界访问
            ++child; // 假如右孩子小，child++
        }
        if (a[child] < a[parent]) {
            swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

这段代码实现的是小根堆的向下调整逻辑。如果要适配大根堆的出堆操作，只需要把两处判断条件的符号修改为'大于'即可：

子节点选择部分：将 a[child + 1] < a[child] 改为 a[child + 1] > a[child]（选出子节点中更大的那个）； 父子节点交换部分：将 a[child] < a[parent] 改为 a[child] > a[parent]（若子节点值大于父节点，执行交换）。

【向下/向上调整算法时间复杂度计算】

1. 向上调整的过程，是从堆的某个叶子节点（新插入节点）向堆顶移动，调整的次数由堆的高度决定。
2. 由于堆是完全二叉树结构，若堆的元素个数为 n，则完全二叉树的高度为 log2(N + 1)。
3. 因此，向上调整算法的时间复杂度为 O(logN)（在数据结构中 log 以 2 为底 N 的对数可以写作 O(logN)）。

（向下调整算法的时间复杂度逻辑一致：从堆顶向叶子节点移动，最大次数也是树的高度，复杂度同样为 O(logN)）

6. 堆的判空、元素个数、取堆顶元素接口

// 取堆顶元素
HpDataType HeapTop(heap* php) {
    assert(php);
    return php->a[0];
}

// 判空
bool HeapEmpty(heap* php) {
    assert(php);
    return php->size == 0;
}

// 堆元素个数
int HeapSize(heap* php) {
    assert(php);
    return php->size;
}

三、堆的应用

1. 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？

① 向下调整建堆

向下调整建堆逻辑：这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆；

建大根堆

// n: 数组中元素的总个数
// 核心逻辑：从最后一个非叶子节点开始，向前逐个调整节点，使每个子树满足堆的性质
// 最后一个非叶子节点的下标计算：
// 数组下标从 0 开始时，最后一个元素的下标是 n-1，它的父节点下标为 (n-1-1)/2
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
    // 对下标为 i 的节点进行"向下调整"，使以 i 为根的子树成为堆
    AdjustDown(a, n, i);
}

② 向上调整建堆

向上调整法建堆：从第 2 个元素（i=1）开始，逐个对每个元素调用 AdjustUp，让新元素向上和父节点比较、交换，直到满足堆的性质，最终把整个数组建成堆；

// 建堆 -- 向上调整建堆
for (int i = 1; i < n; i++) {
    AdjustUp(a, i);
}

这个过程其实相当于模拟堆的插入操作：每往堆里加入一个新元素，就对它做一次向上调整；等所有元素都插入并调整完毕，整个堆也就构建完成了。

【建堆时间复杂度分析】

向下调整建堆：O(N)

向上调整建堆：O(N * logN)

核心差异：

1. 向上调整建堆：低层（数量多）+ 调整次数多（底层节点要逐层往上调，最多需 logN 次），最终总代价是'大量节点 × 多次调整'→ O(N logN)。
2. 向下调整建堆：高层（数量少）+ 调整次数多（根节点要逐层往下调，最多需 logN 次）；低层（数量多）+ 调整次数少（底层节点基本不用调），最终总代价是'少量节点 × 多次调整 + 大量节点 × 少量调整'→ O(N)。

2. 堆排序

**堆排序（升序）思想：**先建大顶堆（堆顶是最大值），再反复将堆顶与堆尾交换（最大值归位），然后调整剩余元素为大顶堆，直到堆空，数组升序。

// 排升序 建大堆 O(N*logN)
void HeapSort_Up(int *a, int n) {
    // 建堆 -- 向下调整建堆 -- O(N)
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    int end = n - 1;
    // 排序 -- O(N*logN)
    while (end > 0) {
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        end--;
    }
}

排降序的话，建小顶堆就行：堆顶始终是当前堆的最小值，把它和堆尾元素交换（最小值就放到了当前未排序区的末尾，逐步归位），再将剩下的元素重新调整为小顶堆，重复这个过程，直到堆处理完，数组就降序排好了。

// 排降序 建小堆 O(N*logN)
void HeapSort_Down(int* a, int n) {
    // 建堆 -- 向上调整建堆 -- O(N*logN)
    for (int i = 1; i < n; i++) {
        AdjustUp(a, i);
    }
    int end = n - 1;
    // 排序 -- O(N*logN)
    while (end > 0) {
        swap(&a[end], &a[0]);
        AdjustDown(a, end, 0);
        end--;
    }
}

3. TOP-K 问题

**TOP-K 问题：**即求数据集合中前 K 个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。对于 Top-K 问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了 (可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前 K 个元素来建堆前 k 个最大的元素，则建小堆；前 k 个最小的元素，则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素

// TOP-K 求前 k 个最大/最小的元素
// 前 k 个最大的元素，则建小堆
// 前 k 个最小的元素，则建大堆
// 当前 n = 15; k = 10;
// 求前 10 个最大的元素：
void TOP_K() {
    // 造数据
    int n = 15;
    int* a = (int*)malloc(sizeof(int) * n);
    srand((unsigned int)time(NULL));
    for (size_t i = 0; i < n; ++i) {
        a[i] = rand() % n + 1;
    }
    int k = 10;
    // 向下调整建堆 -- 建小堆
    for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, 10, i);
    }
    // 接下来剩下的元素和堆顶的元素进行比较
    for (int i = k; i < n; i++) {
        if (a[0] < a[i]) {
            swap(&a[0], &a[i]);
            // 向下调整
            AdjustDown(a, 10, 0);
        }
    }
    // 打印所有数据，观察是否满足
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

四、堆相关选择题

堆的判断需验证序列是否符合'大根堆（父节点≥子节点）'或'小根堆（父节点≤子节点）'的规则。以选项 A [100,60,70,50,32,65] 为例：

根节点 100，左子节点 60、右子节点 70（100≥60 且 100≥70，符合大根堆）；节点 60，左子节点 50、右子节点 32（60≥50 且 60≥32，符合）；节点 70，左子节点 65（70≥65，符合）；所有节点均满足大根堆规则，因此 A 是堆。

只有向下调整建堆的结果，所以选 C