考研全科复习资料

408

数据结构

DS-04-08 堆（大根堆/小根堆）

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	完全二叉树的性质、顺序存储、优先队列概念
知识网络定位	堆是一种特殊的完全二叉树，是优先队列的经典实现，也是堆排序的前置知识
考点热度	H级（高频重点）：近5年出现≥3次，堆的插入/删除操作及堆排序是高频考点

二、知识点讲解

2.1 堆的定义

堆（Heap） 是一棵完全二叉树，且满足以下性质之一：

大根堆（Max-Heap）：每个节点的值 ≥ 其左右子节点的值（根节点最大）
小根堆（Min-Heap）：每个节点的值 ≤ 其左右子节点的值（根节点最小）

关键理解：堆只保证"父 ≥ 子"（大根堆）或"父 ≤ 子"（小根堆），不保证兄弟之间的大小关系。

2.2 堆的顺序存储

堆是完全二叉树，天然适合用数组顺序存储。

大根堆示例：
        90
       /   \
     70     80
    / \    /  \
   50  60 40  30
  / \
 20  10

数组存储（下标从1开始）：
下标：  1   2   3   4   5   6   7   8   9
值：   90  70  80  50  60  40  30  20  10

父子关系（下标从1开始）：

节点 $i$ 的父节点： $\lfloor i/2 \rfloor$
节点 $i$ 的左孩子： $2i$
节点 $i$ 的右孩子： $2i+1$

父子关系（下标从0开始）：

节点 $i$ 的父节点： $\lfloor (i-1)/2 \rfloor$
节点 $i$ 的左孩子： $2i+1$
节点 $i$ 的右孩子： $2i+2$

2.3 堆的插入操作（上滤/Shift-Up）

过程：将新元素放在数组末尾（完全二叉树最后），然后"上滤"——与父节点比较，若违反堆性质则交换，直到满足堆性质。

// 大根堆的插入
// 参数 H：堆数组，n：当前堆大小，x：待插入元素
void MaxHeap_Insert(int H[], int *n, int x) {
    (*n)++;                    // 堆大小加1
    H[*n] = x;                // 新元素放在末尾
    
    int i = *n;                // 当前位置
    // 上滤：与父节点比较，若比父节点大则交换
    while (i > 1 && H[i] > H[i / 2]) {
        swap(H[i], H[i / 2]); // 与父节点交换
        i = i / 2;            // 移动到父节点位置
    }
}

时间复杂度： $O(\log n)$ （最多上滤到根，即树的高度）。

2.4 堆的删除操作（下滤/Shift-Down）

通常删除堆顶元素（最大值/最小值）。

过程：将堆顶与末尾元素交换，删除末尾，然后将新的堆顶"下滤"——与较大的子节点比较，若违反堆性质则交换，直到满足堆性质。

// 大根堆的删除（删除堆顶）
// 参数 H：堆数组，n：当前堆大小
int MaxHeap_Delete(int H[], int *n) {
    int maxVal = H[1];         // 保存堆顶（最大值）
    H[1] = H[*n];             // 将末尾元素放到堆顶
    (*n)--;                    // 堆大小减1
    
    int i = 1;                 // 当前位置
    // 下滤：与较大的子节点比较，若比子节点小则交换
    while (2 * i <= *n) {      // 当有左孩子时
        int child = 2 * i;     // 默认选左孩子
        // 如果有右孩子且右孩子更大，选右孩子
        if (child + 1 <= *n && H[child + 1] > H[child]) {
            child = child + 1;
        }
        if (H[i] >= H[child]) break;  // 已满足堆性质，停止
        swap(H[i], H[child]);          // 与子节点交换
        i = child;                      // 移动到子节点位置
    }
    
    return maxVal;             // 返回被删除的最大值
}

时间复杂度： $O(\log n)$ （最多下滤到叶子，即树的高度）。

2.5 建堆操作（Heapify / Build-Heap）

自底向上建堆：从最后一个非叶子节点开始，依次对每个节点执行下滤操作。

// 对以 i 为根的子树执行下滤（大根堆）
void ShiftDown(int H[], int n, int i) {
    while (2 * i <= n) {
        int child = 2 * i;
        if (child + 1 <= n && H[child + 1] > H[child]) {
            child = child + 1;
        }
        if (H[i] >= H[child]) break;
        swap(H[i], H[child]);
        i = child;
    }
}

// 建堆（自底向上）
// 参数 H：数组（下标从1开始），n：元素个数
void BuildMaxHeap(int H[], int n) {
    // 从最后一个非叶子节点开始，向前逐个下滤
    for (int i = n / 2; i >= 1; i--) {
        ShiftDown(H, n, i);
    }
}

为什么从 $n/2$ 开始？：完全二叉树中，编号 $\lfloor n/2 \rfloor + 1$ 到 $n$ 的节点都是叶子节点，叶子节点无需下滤。

建堆的时间复杂度： $O(n)$ （不是 $O(n\log n)$ ！）

证明：设树高为 $h = \lfloor \log_2 n \rfloor$ 。第 $k$ 层（从下往上， $k=0$ 为叶子层）有至多 $\lceil n/2^{k+1} \rceil$ 个节点，每个节点最多下滤 $k$ 次。总操作数： $T(n) = \sum_{k=0}^{h} \lceil n/2^{k+1} \rceil \cdot k \leq n \sum_{k=0}^{h} k/2^k < n \cdot 2 = O(n)$

2.6 大根堆 vs 小根堆对比表

对比项	大根堆	小根堆
堆顶	最大值	最小值
堆性质	父 ≥ 子	父 ≤ 子
插入时	上滤（比父大则交换）	上滤（比父小则交换）
删除时	下滤（与较大子交换）	下滤（与较小子交换）
应用场景	取最大值、堆排序（升序）	取最小值、堆排序（降序）、Dijkstra算法

2.7 堆的操作复杂度汇总

操作	时间复杂度	说明
插入	$O(\log n)$	最多上滤到根
删除堆顶	$O(\log n)$	最多下滤到叶子
建堆	$O(n)$	自底向上，不是 $O(n\log n)$
查找最大/最小	$O(1)$	堆顶即是最值
查找任意元素	$O(n)$	需遍历

三、记忆与理解辅助

技巧1：堆操作口诀

"插入往上滤，删除往下滤；建堆从中间，自底向上推"
插入：新元素在末尾，与父比较上滤
删除：末尾补堆顶，与子比较下滤
建堆：从 $n/2$ 开始，对每个节点下滤

技巧2：堆 vs 二叉搜索树（BST）

对比项	堆	BST
结构	完全二叉树	任意二叉树
有序性	仅父≥子（或父≤子）	左<根<右
兄弟关系	无序	有序（左<右）
查找效率	$O(n)$	$O(\log n)$
取最值	$O(1)$	$O(\log n)$
主要用途	优先队列、堆排序	有序数据的动态维护

技巧3：下滤时选子节点的判断

大根堆下滤：选较大的子节点交换（保证交换后父≥子） 小根堆下滤：选较小的子节点交换（保证交换后父≤子）
只有一个子节点（左孩子）时直接与左孩子比较。

技巧4：建堆复杂度直觉

建堆 $O(n)$ 而非 $O(n\log n)$ 的直觉：大部分节点在底层，下滤距离很短。高层节点少但下滤距离长，底层节点多但下滤距离短（叶子不用动）。两者平衡后总和是 $O(n)$ 。

四、例题与精解

例题1（基础巩固）

题目：对数组 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]（下标从1开始），执行 BuildMaxHeap，写出建堆过程和最终结果。

命题意图：考查自底向上建堆的完整过程。

审题分析： $n=10$ ，从 $n/2=5$ 开始，对节点5、4、3、2、1依次下滤。

解题思路：从最后一个非叶子节点开始，逐个执行下滤。

完整步骤：

初始数组（下标从1）：

下标:  1  2  3  4  5  6  7  8  9  10
值:    4  1  3  2  16 9  10 14 8  7

完全二叉树：

            4
         /    \
        1       3
       / \     / \
      2   16  9   10
     / \  /
    14 8 7

Step 1：i=5（值16），左孩子=10(值7)，无右孩子。16>7，无需下滤。

Step 2：i=4（值2），左孩子=8(值14)，无右孩子。2<14，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    4  1  3  14 16 9  10 2  8  7

i=8（值2），左孩子=16(超出)，停止。

Step 3：i=3（值3），左孩子=6(值9)，右孩子=7(值10)。max=10(下标7)。3<10，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    4  1  10 14 16 9  3  2  8  7

i=7（值3），左孩子=14(超出)，停止。

Step 4：i=2（值1），左孩子=4(值14)，右孩子=5(值16)。max=16(下标5)。1<16，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    4  16 10 14 1  9  3  2  8  7

i=5（值1），左孩子=10(值7)。1<7，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    4  16 10 14 7  9  3  2  8  1

i=10（值1），无孩子，停止。

Step 5：i=1（值4），左孩子=2(值16)，右孩子=3(值10)。max=16(下标2)。4<16，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    16 4  10 14 7  9  3  2  8  1

i=2（值4），左孩子=4(值14)，右孩子=5(值7)。max=14(下标4)。4<14，交换。

下标:  1  2  3  4  5  6  7  8  9  10
值:    16 14 10 4  7  9  3  2  8  1

i=4（值4），左孩子=8(值2)，无右孩子。4>2，停止。

最终大根堆：

           16
         /    \
        14     10
       / \     / \
      4   7   9   3
     / \  /
    2  8 1

数组：[16, 14, 10, 4, 7, 9, 3, 2, 8, 1]

答案：建堆结果为 [16, 14, 10, 4, 7, 9, 3, 2, 8, 1]。

例题2（中等提升）

题目：设计一个算法，在大根堆中删除指定位置 $i$ 的元素，保持堆性质。分析时间复杂度。

命题意图：考查堆的灵活操作能力，不仅限于删除堆顶。

审题分析：删除非堆顶元素时，需要将末尾元素补到位置 $i$ ，然后可能需要上滤或下滤。

解题思路：将末尾元素放到位置 $i$ ，然后判断是上滤还是下滤。

完整步骤：

// 删除大根堆中下标为 i 的元素
// 参数 H：堆数组，n：堆大小指针，i：待删除位置
int MaxHeap_DeleteAt(int H[], int *n, int i) {
    int deleted = H[i];        // 保存被删除的值
    H[i] = H[*n];             // 末尾元素补到位置 i
    (*n)--;                    // 堆大小减1
    
    if (i > 1 && H[i] > H[i / 2]) {
        // 情况1：比父节点大，需要上滤
        while (i > 1 && H[i] > H[i / 2]) {
            swap(H[i], H[i / 2]);
            i = i / 2;
        }
    } else {
        // 情况2：比父节点小（或就是根），需要下滤
        while (2 * i <= *n) {
            int child = 2 * i;
            if (child + 1 <= *n && H[child + 1] > H[child]) {
                child = child + 1;
            }
            if (H[i] >= H[child]) break;
            swap(H[i], H[child]);
            i = child;
        }
    }
    
    return deleted;
}

时间复杂度： $O(\log n)$ 。上滤最多到根，下滤最多到叶子，都是 $O(\log n)$ 。

方法反思：

删除任意位置的元素是堆排序的基础操作
关键判断：补上来的元素与父比较，决定上滤还是下滤
只需执行上滤或下滤之一，不会两者都执行

五、考情分析

项目	内容
考查频次	近5年约3-4次，高频考点
常见题型	选择题（判断堆、建堆过程）、大题（堆的插入/删除操作、堆排序）
分值占比	选择题2分 + 大题5-10分
命题趋势	建堆过程是选择题常考；堆的插入/删除操作常作为大题考查；堆排序是单独考点但以堆为基础
典型考点	①判断是否为堆 ②建堆过程 ③插入/删除操作 ④建堆的时间复杂度分析

六、易错点提醒

易错点1

错误表现：建堆时从 $n$ 开始（从叶子开始），而不是从 $n/2$ 开始
错误原因：不了解叶子节点无需下滤的事实
正确理解：完全二叉树中，编号 $\lfloor n/2 \rfloor + 1$ 到 $n$ 都是叶子，叶子已经是合法的堆，无需操作

易错点2

错误表现：建堆复杂度误写为 $O(n\log n)$
错误原因：朴素地认为 $n$ 个节点每个最多下滤 $\log n$ 次
正确理解：底层节点多但下滤距离短，顶层节点少但下滤距离长。数学证明总和为 $O(n)$

易错点3

错误表现：下滤时忘记检查右孩子是否存在
错误原因：代码中直接比较左右孩子，没有判断 child+1 <= n
正确理解：必须先判断右孩子是否存在（child+1 <= n），只有右孩子存在时才比较左右孩子

易错点4

错误表现：认为堆中兄弟节点之间有大小关系
错误原因：将堆的性质与 BST 混淆
正确理解：堆只要求父 ≥ 子（大根堆）或父 ≤ 子（小根堆），兄弟之间没有大小关系

易错点5

错误表现：删除堆顶时直接把左孩子或右孩子提上来当堆顶
错误原因：没有理解堆的删除策略
正确理解：删除堆顶后，应将末尾元素补到堆顶位置，然后下滤。这样保证了完全二叉树的结构不被破坏

七、来源标注

依据2026考研统考408大纲
依据《数据结构（C语言版）》严蔚敏版
依据《数据结构》王道考研辅导讲义
建堆 $O(n)$ 复杂度证明依据《算法导论》（CLRS）第6章

408 ​

数据结构 ​

DS-04-08 堆（大根堆/小根堆） ​

一、定位信息 ​

二、知识点讲解 ​

2.1 堆的定义 ​

2.2 堆的顺序存储 ​

2.3 堆的插入操作（上滤/Shift-Up） ​

2.4 堆的删除操作（下滤/Shift-Down） ​

2.5 建堆操作（Heapify / Build-Heap） ​

2.6 大根堆 vs 小根堆对比表 ​

2.7 堆的操作复杂度汇总 ​

三、记忆与理解辅助 ​

技巧1：堆操作口诀 ​

技巧2：堆 vs 二叉搜索树（BST） ​

技巧3：下滤时选子节点的判断 ​

技巧4：建堆复杂度直觉 ​

四、例题与精解 ​

例题1（基础巩固） ​

例题2（中等提升） ​

五、考情分析 ​

六、易错点提醒 ​

易错点1 ​

易错点2 ​

易错点3 ​

易错点4 ​

易错点5 ​

七、来源标注 ​

408