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

一、堆的核心概念与结构特性

堆的本质是满足特定规则的完全二叉树，同时通过数组存储以最大化空间利用率（用连续数组存储完全二叉树，无需额外存储指针，几乎没有内存浪费）。

1. 堆的定义

• 看着像一棵'层层填满、最后一层靠左排'的树（完全二叉树），但实际是存在连续数组里的；
• 有个铁规矩：要么每个节点都比自己的子节点大/相等（这叫大根堆，最顶上的是最大的数），要么每个节点都比自己的子节点小/相等（这叫小根堆，最顶上的是最小的数）；
• 核心用处就是快速找最大/最小数，不用挨个遍历，直接拿最顶上的就行。

2. 核心特性

逻辑结构：必为完全二叉树，不存在'断层'节点，所有叶子节点集中在最后两层，且最后一层节点靠左排列；

存储结构：物理上是连续数组，通过索引映射父子关系（设节点索引为 i）：

父节点索引：(i - 1) / 2（向下取整）；左子节点索引：2 * i + 1；右子节点索引：2 * i + 2；

最值特性：堆顶（数组第一个元素）始终是集合中的最大值（大根堆）或最小值（小根堆）。

3. 直观示例

小根堆：逻辑上根节点最小，数组存储为 [10, 15, 25, 56, 30, 70]；

大根堆：逻辑上根节点最大，数组存储为 [70, 56, 30, 15, 25, 10]。

二、堆的实现

1. 堆的结构

堆的底层是用数组实现的，因此它的结构和顺序表的结构基本一致，具体定义如下：

typedef int HpDataType;
typedef struct Heap {
    HpDataType* a;
    int size;
    int capacity;
} heap;

2. 堆的初始化

// 初始化堆
void HeapInit(heap* php) {
    assert(php);
    php->a = (HpDataType*)malloc(sizeof(HpDataType) * 4);
    if (php->a == NULL) {
        perror("malloc");
        return;
    }
    php->capacity = 4;
    php->size = 0;
}

3. 堆的销毁

// 堆的销毁
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