📌 前言

在之前的数据结构学习中，我们掌握了线性表（顺序表、链表）、栈和队列。这些结构处理数据时，要么按插入顺序（栈/队列），要么按位置（线性表）。但是否存在一种结构，能自动将数据按优先级（如大小）组织，每次都能高效地取出“最大”或“最小”的元素？

堆（Heap） 正是为此而生！它是一种特殊的完全二叉树，通常用数组实现，能在 O(log n) 时间内插入和删除极值，在 O(1) 时间内获取极值。它也是优先队列的底层实现，广泛应用于堆排序、Top-K 问题、Dijkstra 算法等。

本文将带你从零实现一个动态堆（小根堆/大根堆可切换），并基于堆实现堆排序，包含：

• ✅ 堆的结构定义（动态数组）

• ✅ 向上调整（Insert）与向下调整（Delete）

• ✅ 堆的插入、删除、取顶、判空、销毁

• ✅ 堆排序的两种实现（使用堆结构 vs 原地堆排序）

• ✅ 完整测试代码与运行结果

学完你将掌握：
👉 堆的数组存储方式（完全二叉树）
👉 父子结点下标关系：parent = (child-1)/2，left = 2*parent+1，right = 2*parent+2
👉 向上调整和向下调整的核心逻辑
👉 堆排序的原理及 O(n) 建堆方法

---

一、堆的基本概念

1.1 什么是堆

堆是一种完全二叉树，且满足堆性质：

• 大根堆：每个结点的值都 ≥ 其子结点的值（根最大）

• 小根堆：每个结点的值都 ≤ 其子结点的值（根最小）

完全二叉树的特性允许我们用数组高效存储，无需维护左右指针。

1.2 数组存储方式

对于下标 i 的结点（从0开始）：

• 左孩子：2*i + 1

• 右孩子：2*i + 2

• 父结点：(i-1)/2

大根堆示例：

        50
       /  \
     31    43
    /  \  /
   20  10 39

数组形式：[50, 31, 43, 20, 10, 39]

1.3 堆的应用场景

• 堆排序：O(n log n) 不稳定排序

• 优先队列：按优先级处理任务

• Top-K 问题：找最大/最小的 K 个元素

• Dijkstra 最短路径：用堆优化

---

二、堆的代码实现

2.1 头文件 Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int HPDataType;

typedef struct Heap {
    HPDataType* arr;   // 动态数组
    int size;          // 有效元素个数
    int capacity;      // 容量
} HP;

// 辅助函数
void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);

// 基本操作
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPrint(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);
int HPSize(HP* php);

2.2 辅助函数：交换

void Swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

2.3 向上调整（用于插入）

作用：从某个孩子结点开始，向上比较，若破坏堆性质则交换，直到根或满足性质。

void AdjustUp(HPDataType* arr, int child) {
    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;
        }
    }
}

💡 切换大小堆：只需修改 if 中的比较符号即可。

• 小根堆：arr[child] < arr[parent]

• 大根堆：arr[child] > arr[parent]

2.4 向下调整（用于删除堆顶）

作用：从指定父结点开始，向下比较与较大/较小的孩子交换，直到叶子或满足性质。

void AdjustDown(HPDataType* arr, int parent, int n) {
    int child = 2 * parent + 1;   // 左孩子
    while (child < n) {
        // 选出左右孩子中较大/较小的一个（大根堆选大，小根堆选小）
        if (child + 1 < n && arr[child] < arr[child + 1]) {
            child++;   // 右孩子更大（若为大根堆）
        }
        // 比较父与孩子
        if (arr[child] > arr[parent]) {   // 大根堆：孩子 > 父亲则交换
            Swap(&arr[parent], &arr[child]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

⚠️ 注意：上面的 AdjustDown 实现是大根堆版本（因为选了较大的孩子，且当孩子 > 父亲时交换）。若要小根堆，应改为选较小的孩子，且当孩子 < 父亲时交换。
读者可根据需要灵活调整比较符号。

2.5 初始化与销毁

void HPInit(HP* php) {
    php->arr = NULL;
    php->size = php->capacity = 0;
}

void HPDestroy(HP* php) {
    if (php->arr) free(php->arr);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

2.6 插入元素（Push）

void HPPush(HP* php, HPDataType x) {
    assert(php);
    // 扩容逻辑（与顺序表相同）
    if (php->size == php->capacity) {
        int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
        if (tmp == NULL) {
            perror("realloc fail");
            exit(1);
        }
        php->arr = tmp;
        php->capacity = newCapacity;
    }
    php->arr[php->size] = x;
    AdjustUp(php->arr, php->size);
    php->size++;
}

2.7 删除堆顶元素（Pop）

bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

void HPPop(HP* php) {
    assert(!HPEmpty(php));
    // 交换堆顶与最后一个元素
    Swap(&php->arr[0], &php->arr[php->size - 1]);
    php->size--;
    // 向下调整新堆顶
    AdjustDown(php->arr, 0, php->size);
}

2.8 获取堆顶 & 其他

HPDataType HPTop(HP* php) {
    assert(!HPEmpty(php));
    return php->arr[0];
}

int HPSize(HP* php) {
    assert(php);
    return php->size;
}

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

---

三、堆排序的实现

堆排序有两种常见实现方式：

3.1 方式一：使用堆数据结构（HeapSort1）

直接利用上面的堆结构，将所有元素 Push 入堆，然后依次 Pop 堆顶取出有序序列。
特点：代码简单，但需要额外 O(n) 空间。

void HeapSort1(int* arr, int n) {
    HP hp;
    HPInit(&hp);
    for (int i = 0; i < n; i++) {
        HPPush(&hp, arr[i]);
    }
    int i = 0;
    while (!HPEmpty(&hp)) {
        arr[i++] = HPTop(&hp);
        HPPop(&hp);
    }
    HPDestroy(&hp);
}

3.2 方式二：原地堆排序（经典，无额外空间）

步骤：

1. 建堆：将原数组调整成堆结构（大根堆用于升序，小根堆用于降序）。

2. 排序：交换堆顶（最大值）与末尾元素，堆大小减1，再向下调整新堆顶，重复。

void HeapSort(int* arr, int n) {
    // 1. 建堆：从最后一个非叶子结点开始向下调整（O(n)）
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(arr, i, n);
    }

    // 2. 排序
    for (int i = n - 1; i > 0; i--) {
        Swap(&arr[0], &arr[i]);      // 堆顶与末尾交换
        AdjustDown(arr, 0, i);       // 缩小堆范围并调整
    }
}

💡 为什么升序建大根堆？
大根堆的堆顶是最大值，交换到数组末尾后，最大值固定，再对剩余部分建大根堆，重复得到升序序列。

建堆复杂度分析

• 向下调整建堆：从倒数第二层开始，结点数多但调整次数少，总复杂度 O(n)。

• 向上调整建堆（逐个插入）：复杂度 O(n log n)，效率较低。

---

四、测试代码与运行结果

4.1 测试堆的插入与删除（test1、test2）

#include "Heap.h"

void test1() {
    HP hp;
    HPInit(&hp);
    HPPush(&hp, 10);
    HPPush(&hp, 31);
    HPPush(&hp, 20);
    HPPush(&hp, 43);
    HPPush(&hp, 50);
    HPPush(&hp, 39);
    HPPrint(&hp);   // 小根堆结果：10 31 20 43 50 39 ？实际顺序取决于调整
}

void test2() {
    HP hp;
    HPInit(&hp);
    HPPush(&hp, 10);
    HPPush(&hp, 31);
    HPPush(&hp, 20);
    HPPush(&hp, 43);
    HPPush(&hp, 50);
    HPPush(&hp, 39);
    HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
    HPPop(&hp); HPPrint(&hp);
}

4.2 测试堆排序

void test4() {
    int arr[6] = {20, 10, 31, 40, 50, 43};
    printf("排序前：");
    for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
    printf("\n");
    
    HeapSort(arr, 6);   // 原地堆排序（升序）
    printf("排序后：");
    for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
    printf("\n");
}

运行结果（大根堆升序）：

排序前：20 10 31 40 50 43
排序后：10 20 31 40 43 50

---

五、复杂度分析

操作	时间复杂度	说明
插入（Push）	O(log n)	向上调整最多树高
删除堆顶（Pop）	O(log n)	向下调整最多树高
取堆顶（Top）	O(1)	直接返回 arr[0]
建堆（向下调整）	O(n)	高效建堆方法
堆排序（整体）	O(n log n)	建堆 O(n) + n次调整
空间复杂度	O(1)（原地排序）	只需常量额外空间

---

六、堆排序的图解与核心细节

6.1 向下调整建堆过程

以数组 [20, 10, 31, 40, 50, 43] 为例，建大根堆：

1. 从最后一个非叶子结点下标 (n-1-1)/2 = 2（值为31）开始向下调整。

2. 调整后，再对下标1（10）、下标0（20）依次调整。

3. 最终得到大根堆 [50, 40, 43, 10, 20, 31]。

6.2 排序过程

• 交换堆顶50与末尾31 → [31, 40, 43, 10, 20, 50]，堆大小减1。

• 向下调整前5个元素 → [43, 40, 31, 10, 20, 50]。

• 重复直到全部有序。

---

七、常见问题与优化建议

7.1 如何切换大根堆/小根堆？

只需修改 AdjustUp 和 AdjustDown 中的比较符号。例如：

• 大根堆：AdjustUp 中 arr[child] > arr[parent]；AdjustDown 中选较大孩子，且 arr[child] > arr[parent]。

• 小根堆：AdjustUp 中 arr[child] < arr[parent]；AdjustDown 中选较小孩子，且 arr[child] < arr[parent]。

7.2 为什么向下调整建堆是 O(n)？

因为从倒数第二层开始，结点数多但每个结点调整次数少（接近1次），总工作量呈几何级数收敛，最终为 O(n)。
向上调整建堆（逐个插入）每个结点调整 log k 次，总和 O(n log n)。

7.3 堆排序的不稳定性

堆排序在交换过程中可能改变相同值的相对顺序，因此是不稳定排序。

---

八、总结

通过本文，我们完整实现了堆这种高效的数据结构，并掌握了两种堆排序方法：

• ✅ 堆的核心操作：向上调整（插入）和向下调整（删除）

• ✅ 动态数组实现，支持自动扩容

• ✅ 原地堆排序，空间 O(1)，时间 O(n log n)

• ✅ 建堆的两种方式及复杂度分析

堆是优先队列的基础，也是很多算法优化（如求Top-K、中位数）的关键。建议读者亲手画图模拟 Push 和 Pop 过程中数组的变化，理解调整的过程。