Lesson 39: 堆与 Top-K

练习任务

难度：难

实现堆数据结构并解决经典的 Top-K 问题——从海量数据中找出最大的 K 个数。你需要完成三个核心函数：

heapify(arr, n, i) — 向下调整（小顶堆：让节点 i "下沉"到正确位置）
build_heap(arr, n) — 建堆：从最后一个非叶节点开始，自底向上构建小顶堆
top_k(arr, n, k) — Top-K：输出 arr 中最大的 k 个数（降序打印）

swap 辅助函数和 main 输入解析已提供。

本课共有 2 组测试用例：

输入 "5 3 8 1 9 2\n3\n"  → 输出 "9 8 5"
输入 "5 3 8 1 9 2\n1\n"  → 输出 "9"

提示：Top-K 的核心洞察是——找最大的 K 个，用小顶堆维护"门槛"。堆顶永远是 K 个中最小的那个，新元素若比门槛大，替换堆顶并下沉；若比门槛小，直接丢弃。思考方向：为什么大顶堆不行？大顶堆的堆顶是最大值——你用它做什么？

核心知识点

完全二叉树 ↔ 数组映射 — 堆用数组紧凑存储：父 (i-1)/2、左子 2i+1、右子 2i+2，无需指针
heapify 前提与下滤（sift-down） — 左右子树已是合法堆，当前根可能违反堆性质，需要下沉至正确位置
build_heap 自底向上 O(n) — 从 n/2-1 向 0 逐节点 heapify，附 Σ 收敛证明（不是 O(n log n)）
Top-K 用小顶堆的核心洞察 — 堆顶 = 阈值 = K 个候选中的最小值，与当前元素比较决定取舍
"最大 K 用小堆"的反直觉陷阱 — 常见面试误导点的完整拆解：为什么直觉驱使你选大顶堆，以及大顶堆真正失败的原因
流式 Top-K O(k) 空间 — 只维护大小为 k 的堆，数据逐批流入，无需一次性加载全量数据
堆排 vs 快排：最坏保证 vs 缓存友好 — 堆排最坏 O(n log n) 但缓存不友好；快排平均快但最坏 O(n²)；introsort 将两者结合

代码框架

39_heap_base_topk.c

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

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

/* 小顶堆下沉：确保以 i 为根的子树满足堆性质
 * 比较 i 和它的左右孩子，如果 i 不是最小的，与较小的孩子交换 */
void heapify(int arr[], int n, int i) {
    // ① 假设 i 是最小的：smallest = i; l = 2*i+1; r = 2*i+2

    // ② 如果左孩子在范围内且比 arr[smallest] 小 → smallest = l

    // ③ 如果右孩子在范围内且比 arr[smallest] 小 → smallest = r

    // ④ 如果 smallest != i：交换 arr[i] 和 arr[smallest]
    //    递归 heapify(arr, n, smallest) 继续下沉
}

/* 建堆：从最后一个非叶节点开始（n/2 - 1），向前逐个 heapify
 * 自底向上保证每个子树都是合法的小顶堆 */
void build_heap(int arr[], int n) {
    // 在这里实现 build_heap:
    // for (i = n/2 - 1; i >= 0; i--) heapify(arr, n, i)
}

/* Top-K：用大小为 k 的小顶堆维护最大的 k 个数
 * 1. 取前 k 个元素建堆
 * 2. 遍历剩余元素：如果当前元素 > 堆顶（门槛），替换堆顶并下沉
 * 3. 堆中元素从大到小排序输出
 * 注意：需要动态分配大小为 k 的堆数组 */
void top_k(int arr[], int n, int k) {
    // ① malloc 一个大小为 k 的堆数组

    // ② 将 arr 的前 k 个元素拷入堆中

    // ③ build_heap(heap, k)

    // ④ 遍历剩余元素 i = k..n-1：
    //    如果 arr[i] > heap[0]（比门槛大）：
    //      heap[0] = arr[i]; heapify(heap, k, 0)

    // ⑤ 堆中元素排序输出（从大到小）：
    //    用 heap sort 思想：逐个将堆顶（最小值）交换到末尾，再 heapify 缩小范围
    //    最后从后往前打印 k 个元素

    // ⑥ free(heap)
}

int main(void) {
    char line1[1024], line2[32];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);

    int arr[1024], n = 0, k;

    /* 解析第一行数字 */
    char *tok = strtok(line1, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }

    sscanf(line2, "%d", &k);
    top_k(arr, n, k);
    return 0;
}

阅读骨架后，尝试自己填充 // ① 到 // ⑥ 标记的部分。核心挑战在于：heapify 的三个指针——smallest、left、right——如何运作？build_heap 为什么从 n/2-1 开始而不是从 0？Top-K 中堆顶和门槛是什么关系？输出时怎样把堆中的 k 个最小变成最大 k 个的降序？

TIP

先不要往下翻看参考解答。用 arr = [5, 3, 8, 1, 9, 2], k=3 在纸上完整追踪一遍 Top-K 的全过程。重点关注"门槛"的化变——从 3 开始，每步如何变化。

深度讲解

1. 完全二叉树与数组索引映射——堆的物理表示

1.1 堆是一棵完全二叉树

堆（Heap）是一棵完全二叉树（Complete Binary Tree）——除了最后一层，其他每一层都是满的，且最后一层的节点从左到右连续排列。这个看似简单的性质，赋予了堆一个非常强大的特性：可以用数组紧凑存储，无需指针。

完全二叉树（与非完全二叉的对比）：

  完全二叉树 ✓                非完全二叉树 ✗
        A                          A
      /   \                      /   \
     B     C                    B     C
    / \   /                    / \     \
   D   E F                    D   E     F   ← 最后一层有空隙

1.2 索引映射公式推导

由于完全二叉树的节点按层序（从上到下、从左到右）连续排列，把节点放入数组时，父子关系可以通过纯算术运算得到——不需要额外存储指针。

数组索引与树节点的对应关系（0-based）：

             arr[0]
            /      \
       arr[1]      arr[2]
       /    \       /    \
    arr[3] arr[4] arr[5] arr[6]
     /  \
arr[7] arr[8] ...

对于节点 i:
  父节点:  (i - 1) / 2         （整数除法）
  左孩子:  2*i + 1
  右孩子:  2*i + 2
  是否是叶子:  i >= n/2        （后半部分都是叶子）
  最后一个非叶节点:  n/2 - 1

index_mapping.c

/* 索引映射的三个核心公式 */
int parent(int i)   { return (i - 1) / 2; }
int left(int i)     { return 2 * i + 1; }
int right(int i)    { return 2 * i + 2; }

/* 验证: 以 n=5 的数组为例 */
// arr = [3, 1, 5, 8, 2]
//
//  arr[1]=1 的父: (1-1)/2 = 0 → arr[0]=3 ✓
//  arr[2]=5 的父: (2-1)/2 = 0 → arr[0]=3 ✓
//  arr[0]=3 的孩子: left=1(arr[1]=1), right=2(arr[2]=5) ✓
//  arr[1]=1 的孩子: left=3(arr[3]=8), right=4(arr[4]=2) ✓
//
//  n/2 = 2 → 索引 2~4 是叶子: arr[2]=5, arr[3]=8, arr[4]=2 ✓
//  最后一个非叶: n/2-1 = 1 → arr[1]=1 ✓

完整示例: arr = [3, 1, 5, 8, 2], n=5

索引:  0  1  2  3  4
值:    3  1  5  8  2

树形:
        3(0)
       /    \
      1(1)  5(2)
     /  \
   8(3) 2(4)

非叶节点: arr[0]=3, arr[1]=1     (索引 0..n/2-1 = 0..1)
叶子节点: arr[2]=5, arr[3]=8, arr[4]=2  (索引 n/2..n-1 = 2..4)

IMPORTANT

叶子节点的判定公式 i >= n/2 非常关键。在 heapify 中遇到叶子节点时，直接返回（没有孩子可以比较）。在 build_heap 中，从 n/2-1 开始正是因为有孩子的节点才需要调整——叶子节点天然满足堆性质。

1.3 大顶堆 vs 小顶堆：两种堆序

	大顶堆 (Max-Heap)	小顶堆 (Min-Heap)
堆性质	父节点 ≥ 所有后代	父节点 ≤ 所有后代
堆顶	最大值	最小值
获取极值复杂度	O(1)	O(1)
用途	堆排序（升序）、优先队列取最大	优先队列取最小、Dijkstra
Top-K 用途	找最小的 K 个	找最大的 K 个 ← 本题

大顶堆:                小顶堆:
    9                      1
   / \                    / \
  5   7                  3   2
 / \ / \                / \ / \
1  3 2  4              9  5 7  4

堆顶 9 = 最大值         堆顶 1 = 最小值

NOTE

堆只保证父子之间的大小关系，不保证兄弟节点之间的顺序。例如上图中大顶堆的 arr=[9,5,7,1,3,2,4]——5 和 7 的大小关系不确定，1、3、2、4 之间也没有排序。堆是"弱序"结构，只保证从任意节点到根的路径有序。

2. heapify——下滤（sift-down）的核心机制

2.1 heapify 的前提条件

heapify(arr, n, i) 是堆的核心操作。它的前提假设是：

节点 i 的左右子树已经是合法的堆，但 i 本身可能违反堆性质。

这个前提非常关键——它意味着 heapify 只需要"修"一个节点：把根下沉到正确位置，沿途的子堆不需要额外调整。

heapify 的可视化前提:

       i(违反)            ← 只有它可能违规
      /      \
    左(合法)  右(合法)     ← 它们各自是合法的堆！
   /  \     /  \
  ... ...   ... ...

CAUTION

如果堆的左右子树不是合法的堆，仅调用一次 heapify 不能修复整个树。这就是为什么 build_heap 必须自底向上——保证在调用 heapify(i) 时 i 的孩子子树已经是堆。

2.2 小顶堆 heapify 完整逐步跟踪

heapify_min_heap.c

void heapify(int arr[], int n, int i) {
    int smallest = i;           // 假设 i 最小
    int left  = 2 * i + 1;     // 左孩子索引
    int right = 2 * i + 2;     // 右孩子索引

    // 左孩子在范围内且比当前最小更小
    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    // 右孩子在范围内且比当前最小更小
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    // 如果最小不是 i，交换并继续下沉
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);  // 递归下沉
    }
}

以 arr = [5, 1, 8, 3, 2], n=5 为例，调用 heapify(arr, 5, 0)：

初始状态:
        5(0)           ← i=0, 左右子树[1,8] 和 [3,2] 都已是合法小顶堆
       /    \
     1(1)   8(2)
    /  \
  3(3) 2(4)

══════════════════════════════════════
步骤 1: heapify(arr, 5, 0) — 节点 5
══════════════════════════════════════
  left=1(arr[1]=1), right=2(arr[2]=8)
  min(5, 1, 8) = 1 → smallest = 1
  smallest ≠ i → 交换 arr[0] ↔ arr[1]

        1(0)
       /    \
     5(1)   8(2)     ← 5 下沉到位置 1
    /  \
  3(3) 2(4)

══════════════════════════════════════
步骤 2: heapify(arr, 5, 1) — 节点 5 继续下沉
══════════════════════════════════════
  left=3(arr[3]=3), right=4(arr[4]=2)
  min(5, 3, 2) = 2 → smallest = 4
  交换 arr[1] ↔ arr[4]

        1(0)
       /    \
     2(1)   8(2)
    /  \
  3(3) 5(4)

══════════════════════════════════════
步骤 3: heapify(arr, 5, 4) — 节点 5 已是叶子
══════════════════════════════════════
  left=9 >= n, right=10 >= n → 直接返回

结果: [1, 2, 8, 3, 5] — 合法小顶堆 ✓
      堆顶 arr[0]=1 = 最小值

2.3 递归 vs 迭代：两种实现风格

heapify_iterative.c

/* 迭代版 heapify——避免递归调用栈 */
void heapify_iter(int arr[], int n, int i) {
    while (1) {
        int smallest = i;
        int left  = 2 * i + 1;
        int right = 2 * i + 2;

        if (left  < n && arr[left]  < arr[smallest])
            smallest = left;
        if (right < n && arr[right] < arr[smallest])
            smallest = right;

        if (smallest == i) break;     // 已在正确位置，停止

        swap(&arr[i], &arr[smallest]);
        i = smallest;                 // 继续以新位置为根下沉
    }
}

实现	优点	缺点
递归	代码简洁，概念清晰	最坏 O(log n) 递归栈，极端深度可能溢出
迭代	无递归栈开销，更安全	代码稍长，需要 while 循环

在 LeetCode 等在线评测平台中，递归 heapify 通常足够（堆深 O(log n) 远小于默认栈大小 8MB）。工程代码中迭代版更常见。

3. build_heap——建堆与 O(n) 复杂度的严格证明

3.1 从 n/2-1 向上建堆的正确性

build_heap.c

void build_heap(int arr[], int n) {
    // 从最后一个非叶节点开始，向前到 0
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

为什么从 n/2-1 开始？为什么是逆向？

关键论证:

  1. 叶子节点(i >= n/2)天然是合法的堆(没有孩子=不违反堆性质)
  2. 从 n/2-1 向前处理，保证在调用 heapify(i) 时：
     i 的所有孩子子树都已经被处理过 → 是合法堆 ✓
  3. 这就是 heapify 的前提条件！

  n/2-1 = 最后一个非叶节点
          ↓
  ┌───┬───┬───┬───┬───┐
  │ 0 │ 1 │...│n/2-1│ n/2 │...│ n-1 │
  └───┴───┴───┴─────┴─────┴───┴─────┘
  └─── 非叶节点(需要调整) ──┘└── 叶子(无需调整) ──┘
                             从后往前 ←

具体示例: arr = [5, 3, 8, 1, 2], n=5

n/2-1 = 1 → 从 arr[1]=3 开始

步骤 1: heapify(arr, 5, 1) — 节点 arr[1]=3
  孩子: arr[3]=1, arr[4]=2 → min=1 < 3 → 交换 arr[1]↔arr[3]
  [5, 1, 8, 3, 2]

步骤 2: heapify(arr, 5, 0) — 节点 arr[0]=5
  孩子: arr[1]=1, arr[2]=8 → min=1 < 5 → 交换 arr[0]↔arr[1]
  [1, 5, 8, 3, 2]
  5 继续下沉: 孩子arr[3]=3,arr[4]=2 → min=2 < 5 → 交换 arr[1]↔arr[4]
  [1, 2, 8, 3, 5] — 合法小顶堆 ✓

WARNING

如果正向建堆（从 0 到 n-1），你的 heapify 会因为子树可能不是堆而失效——heapify 的前提条件不成立。许多初学者在这里犯错，结果得到一个"看起来差不多但实际不合法"的堆。

3.2 O(n) 复杂度证明：Σ 收敛推导

初看 build_heap：n/2 次 heapify 调用，每次 heapify 最坏 O(log n)，似乎复杂度是 O(n log n)。但这是一个粗糙上界——大多数节点下沉的高度远小于 log n。

精确分析：

设树的高度为 h = ⌊log₂ n⌋，节点按层编号：
  - 第 0 层（最底层，叶子）：有 ~n/2 个节点，下沉高度 0
  - 第 1 层（倒数第二层）：   有 ~n/4 个节点，下沉高度 ≤ 1
  - 第 2 层：                有 ~n/8 个节点，下沉高度 ≤ 2
  - ...
  - 第 h 层（根）：          有 1 个节点，   下沉高度 ≤ h

总下沉次数 ≤ Σ(i=0..h) (n / 2^{i+1}) × i

数学推导：

设 T(n) = build_heap 的总下沉操作次数

T(n) = Σ(i=0..h) (n / 2^{i+1}) × i
     = (n/2) × Σ(i=0..h) (i / 2^i)

令 S(h) = Σ(i=0..h) (i / 2^i)
     = 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + ...

已知无穷级数 Σ(i=0..∞) (i / 2^i) = 2

（推导：S = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...
        S/2 =      1/4 + 2/8 + 3/16 + 4/32 + ...
        S - S/2 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ... = 1
        S/2 = 1 → S = 2）

因此 S(h) ≤ S(∞) = 2

T(n) = (n/2) × S(h) ≤ (n/2) × 2 = n

∴ build_heap 的时间复杂度为 O(n) ∎

3.3 直观理解：为什么大多数节点几乎不下沉？

以 n=15 的满二叉树为例:

            ●              ← 第 3 层: 1 个节点，最坏下沉 3 层
          /     \
         ●       ●          ← 第 2 层: 2 个节点，最坏下沉 2 层
        / \     / \
       ●   ●   ●   ●        ← 第 1 层: 4 个节点，最坏下沉 1 层
      / \ / \ / \ / \
     ● ● ● ● ● ● ● ●        ← 第 0 层: 8 个节点，下沉 0 层（叶子！）

第 0 层: 8 个节点 × 0 = 0
第 1 层: 4 个节点 × 1 = 4
第 2 层: 2 个节点 × 2 = 4
第 3 层: 1 个节点 × 3 = 3

总计: 0 + 4 + 4 + 3 = 11 ≈ O(15) = O(n) ✓

若用 O(n log n) 估算: 15 × 3 = 45，高估了 4 倍！

越接近底层，节点越多但下沉越少——"工作量"自我平衡！

IMPORTANT

build_heap 的 O(n) 特性是堆的重要优势之一。与排序的 Ω(n log n) 下界不同，建堆不需要"全序"——只需要"堆序"（partial order）。"部分有序"使得复杂度可以降到 O(n)。这是算法设计中"降低目标以获取效率"的经典案例。

4. Top-K 用小顶堆——核心洞察

4.1 为什么是小顶堆？门槛直觉

Top-K 问题：从 n 个数中找出最大（或最小）的 K 个。以"找最大的 K 个"为例，为什么要用小顶堆？

核心直觉——把问题反过来思考：

  你要找的是"最大的 K 个"。
  等价于：维护 K 个"候选人"，淘汰不合格的。

  堆顶 = K 个候选人中"最弱的" = 淘汰线（门槛）
  
  新元素 > 堆顶？→ 它能取代最弱的候选人 ← 可以用小顶堆
  新元素 ≤ 堆顶？→ 连最弱的都打不过，淘汰

  所以小顶堆的堆顶 = 动态门槛均—始终是 K 个中最小值！

NOTE

这个视角转换是理解 Top-K 的关键。不要想"我要装最大的 K 个"——要想"我需要知道什么时候一个元素够格进入 K 个最大值的俱乐部"。俱乐部的"会员卡门槛"就是堆顶——K 个中最小（最弱）的那个。

4.2 Top-K 算法逐步演示

top_k_algorithm.c

void top_k(int arr[], int n, int k) {
    int *heap = malloc(k * sizeof(int));

    // 步骤 1: 前 k 个元素建小顶堆
    for (int i = 0; i < k; i++)
        heap[i] = arr[i];
    build_heap(heap, k);           // heap[0] 现在是 k 个中最小值

    // 步骤 2: 遍历剩余元素——门槛淘汰
    for (int i = k; i < n; i++) {
        if (arr[i] > heap[0]) {    // 比门槛大 → 有资格
            heap[0] = arr[i];      // 替换门槛
            heapify(heap, k, 0);   // 恢复堆性质 → 新门槛浮现
        }
        // arr[i] <= heap[0] → 连门槛都够不着，直接丢弃
    }

    // 步骤 3: 堆中 k 个是最大的，但堆序不是降序——需要排序输出
    ...
}

以 arr = [5, 3, 8, 1, 9, 2], n=6, k=3 完整追踪：

═══════════════════════════════════════════════════
步骤 1: 前 3 个元素 [5, 3, 8] 建小顶堆
═══════════════════════════════════════════════════
  build_heap([5, 3, 8], 3):

  树形:      5             3             3
            / \   →      / \   →      / \
           3   8        5   8        5   8
           (无调整)     heapify(0)   完成
                            5↔3

  heap = [3, 5, 8], 堆顶 = 3 (门槛 = 3)
  ┌───┬───┬───┐
  │ 3 │ 5 │ 8 │   ← 最小的 3 个: {3, 5, 8}
  └───┴───┴───┘

═══════════════════════════════════════════════════
步骤 2: i=3, arr[3]=1
═══════════════════════════════════════════════════
  1 ≤ 3(堆顶) → 跳过！"1 连门槛都够不着"
  heap 不变: [3, 5, 8], 门槛仍为 3

═══════════════════════════════════════════════════
步骤 3: i=4, arr[4]=9
═══════════════════════════════════════════════════
  9 > 3(堆顶) → 替换! 门槛提高!
  heap[0] = 9:        [9, 5, 8]
  heapify(heap, 3, 0):

      9(0)             5(0)
     /  \     →       /  \
   5(1) 8(2)         9(1) 8(2)

  heap = [5, 9, 8], 堆顶 = 5 (新门槛 = 5!)

═══════════════════════════════════════════════════
步骤 4: i=5, arr[5]=2
═══════════════════════════════════════════════════
  2 < 5(堆顶) → 跳过！"2 不够格"
  heap 不变: [5, 9, 8]

═══════════════════════════════════════════════════
最终: heap = [5, 9, 8]
  堆中元素 = {5, 9, 8} → 正是最大的 3 个 (按大小: 9, 8, 5) ✓
═══════════════════════════════════════════════════

关键观察：门槛从 3（初始 k 中的最小）逐步升高到 5（实际数据中的第 k 大），这正是"动态门槛"的体现。门槛一旦升高，后面来的元素需要跨过更高的门槛才能进入。

4.3 大顶堆为什么不行？

错误方案（大顶堆找最大 K 个）:

  用前 K 个建大顶堆 → 堆顶 = K 个中最大值
  
  遍历 arr[i]:
    要不要替换？
    堆顶是 K 个中最大值 → 任何比堆顶小的都可能也应该被保留
    堆顶是 K 个中最大值 → 你不知道该淘汰谁！
    
  你面对的是"最大值"——而不是淘汰门槛。
  实际上你需要知道谁"最小"来淘汰，但大顶堆告诉你是谁"最大"！

具体反例: arr = [5, 3, 1, 9, 2], k=3
  建大顶堆(前3个): [5, 3, 1] → 堆顶=5(最大值)
  
  arr[3]=9: 9 > 5 → 替换堆顶 → [9, 3, 1] ← 9确实该进
  arr[4]=2: 2 < 9 → 该不该替换?
    如果替换: 淘汰了谁? 淘汰 9? ← 错误!
    如果不替换: 最终堆中 [9, 3, 1] → 缺了 5!
  
  正确答案(3个最大): 9, 5, 3
  大顶堆最终: 9, 3, 1 ← 少了 5, 多了 1!

5. "最大 K 用小堆"的阈值语义陷阱——面试必考

5.1 陷阱：直觉与算法的冲突

这可能是 Top-K 问题中最经典、被问次数最多的点，面试官很可能这样问：

"你要找最大的 K 个，为什么不用大顶堆？大顶堆的堆顶不就是最大值吗？"

陷阱在于——你需要的不是"K 个中的最大值"，而是"决定一个新元素能否进入 K 个最大值的淘淘线"。淘汰线必须是 K 个中最小的，这样新元素比淘汰线大才能进来。

直觉思维 vs 算法思维:

  ❌ 直觉: "找最大的" → 自然联想到"用最大堆" → 陷入淘汰困境
  ✓ 算法: "我要维护 K 个最大值的候选池"
         → 候选池的淘汰线是 K 个中最小的
         → 所以用小顶堆

  关键洞察: "最大"和"最小"不是矛盾，而是协作——
  
  小顶堆的"最小堆顶"恰恰服务于"找最大元素"的目标！
  它扮演"守门人"的角色——只有够大的元素才能通过。

5.2 完整的对应关系表

你要找的目标	用哪种堆	堆顶是什么	淘汰条件	比较操作
最大的 K 个	小顶堆	K 个中最小值	比堆顶还小	`arr[i] > heap[0]`
最小的 K 个	大顶堆	K 个中最大值	比堆顶还大	`arr[i] < heap[0]`
第 K 大的数	小顶堆	同找最大 Top-K	同找最大 Top-K	`arr[i] > heap[0]`
第 K 小的数	大顶堆	同找最小 Top-K	同找最小 Top-K	`arr[i] < heap[0]`

IMPORTANT

记忆口诀：目标与堆顶相反——找大用小堆，找小用大堆。用"小顶堆实现大目标"虽然反直觉，但理解了"门槛 = 淘汰线"之后就会变得自然。每次面试前默念三遍。

另一个思考角度——"第 K 大"问题：

  找第 K 大的数 = 维护大小为 k 的"前 K 大"集合
  
  用小顶堆维护：
    堆顶 = K 中最小值 = 恰好是第 K 大的值！
    
  arr = [3, 1, 4, 1, 5, 9, 2, 6], k=3
  
  实际排序: 9, 6, 5, 4, 3, 2, 1, 1
  第 3 大 = 5
  
  小顶堆最终: [5, 6, 9] → 堆顶 5 = 第 3 大 ✓

6. 流式 Top-K——O(k) 空间的工程价值

6.1 问题场景：数据放不进内存

Top-K 的优势不仅在于 O(n log k) 的时间复杂度——更关键的工程价值在于 O(k) 空间复杂度。

场景: 10 亿条日志记录，找访问最频繁的 Top 100 个 IP

  全量排序: 需要 10 亿 × 4 字节 = 4GB 内存（至少）
  Top-K 方法: 只需维护 100 个元素的小顶堆 = 400 字节 + 临时缓冲区
  
  数据可以分批次从磁盘/网络读入，每次只比较当前这批与堆顶！

6.2 流式 Top-K 实现

streaming_topk.c

/*
 * 流式 Top-K：数据可以从任意来源分批流入，
 * 只需维护一个大小为 k 的小顶堆。
 * 以下用文件读取模拟流式场景。
 */
#include <stdio.h>
#include <stdlib.h>

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

void heapify(int arr[], int n, int i) {
    int smallest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] < arr[smallest]) smallest = l;
    if (r < n && arr[r] < arr[smallest]) smallest = r;
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

void build_heap(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--)
        heapify(arr, n, i);
}

/*
 * streaming_top_k: 流式处理，每次读一批数据
 * 内存中只保留堆 + 一个读缓冲区
 */
void streaming_top_k(const char *filename, int k) {
    FILE *fp = fopen(filename, "r");
    if (!fp) return;

    int *heap = malloc(k * sizeof(int));
    int val, count = 0;
    int batch[1024], batch_size;

    /*
     * 第一阶段: 先在堆中积累足够 k 个元素
     * 用分批读取确保不限内存
     */
    while (count < k && fscanf(fp, "%d", &val) == 1) {
        heap[count++] = val;
    }
    if (count < k) {
        // 数据量不足 k 个——降级处理
        fclose(fp);
        free(heap);
        return;
    }
    build_heap(heap, k);  // 初始建堆

    /*
     * 第二阶段: 流式处理剩余数据
     * 每次只读一批，与堆顶比较
     */
    while (1) {
        batch_size = 0;
        for (int i = 0; i < 1024; i++) {
            if (fscanf(fp, "%d", &val) != 1) break;
            batch[batch_size++] = val;
        }
        if (batch_size == 0) break;  // 文件读完

        for (int i = 0; i < batch_size; i++) {
            if (batch[i] > heap[0]) {   // 比门槛大
                heap[0] = batch[i];
                heapify(heap, k, 0);    // 调整门槛
            }
        }
    }

    fclose(fp);

    // 排序输出...
    for (int i = k-1; i > 0; i--) {
        swap(&heap[0], &heap[i]);
        heapify(heap, i, 0);
    }
    for (int i = k-1; i >= 0; i--)
        printf("%d ", heap[i]);
    printf("\n");

    free(heap);
}

流式 Top-K 的空间分析:

  固定空间:
    heap[k]          = k 个 int = 4k 字节    (假设 k=100, 400 字节)
    batch[batch_max] = 缓冲区                 (可配置，如 4KB)

  与 n 无关！无论数据是 1GB 还是 100GB，内存只占用 O(k)。

  这是 Top-K 在工程中的核心价值——
  不只是"算法更快"，而是"让本来不可能的任务变得可能"。

TIP

在 C 工程中，对于超大文件（>5GB）的场景，配合 mmap 或零拷贝技术，可以将磁盘 I/O 开销进一步降低。此时瓶颈从"内存容量"变为"磁盘带宽"，Top-K O(k) 空间的优势更加凸显。

7. 堆排序 vs 快速排序——最坏保证与缓存的权衡

7.1 各自优劣分析

维度	堆排序	快速排序
最坏时间复杂度	O(n log n) 严格保证	O(n²)（有序数组 / 全等数组）
平均时间复杂度	O(n log n)	O(n log n)，常数因子更小
空间复杂度	O(1) 原地排序	O(log n) 递归栈（原地分区）
稳定性	不稳定	不稳定（稳定版需额外空间）
缓存友好度	差——跳跃访问	好——顺序扫描分区
最优场景	无特殊优势	随机数组极快

为什么堆排序缓存不友好？

堆排序的访问模式——典型的"跳跃访问":

  堆排过程: 反复交换 heap[0] 和 heap[end], 然后 heapify(0)
  
  堆的父子关系: parent→child 是 2i+1/2i+2
  这导致访问模式在数组两端跳来跳去:
  
    0 → 1 → 3 → 7 → ...
    └─── 跳跃越来越大 ───┘
  
  每一跳都可能 cache miss——CPU 缓存行(64字节)按顺序预读，
  但堆访问经常跳过缓存行边界。

  快排则相反: 两个指针从两端向中间逼近，分区时连续扫描，
  充分利用了 CPU 的缓存预取机制。

7.2 introsort——取两者之长的智慧结合

introsort（内省排序）是 C++ std::sort 的底层实现，它将快排和堆排的优势结合：

introsort 的策略:

  1. 默认: 使用快速排序（利用其缓存友好、常数因子小的优势）
  2. 监控递归深度: 若递归深度超过 ⌊log₂ n⌋ × 2，说明快排退化了
     → 切换到堆排序（保证最坏 O(n log n)）
  3. 小数组优化: 长度小于阈值(通常 16)时，切换到插入排序
     （小数组上插入排序常数因子更优）

introsort_concept.c

/* introsort 的概念示意（非完整实现） */
#define THRESHOLD 16

void introsort(int arr[], int n) {
    introsort_impl(arr, 0, n - 1, 2 * floor_log2(n));
}

void introsort_impl(int arr[], int lo, int hi, int depth_limit) {
    int n = hi - lo + 1;

    // 小数组 → 插入排序
    if (n <= THRESHOLD) {
        insertion_sort(arr + lo, n);
        return;
    }

    // 递归深度过深 → 快排退化，切换到堆排
    if (depth_limit == 0) {
        heap_sort_range(arr, lo, hi);
        return;
    }

    // 正常情况 → 快速排序
    int pivot = partition(arr, lo, hi);
    introsort_impl(arr, lo, pivot - 1, depth_limit - 1);
    introsort_impl(arr, pivot + 1, hi, depth_limit - 1);
}

introsort 的智慧:

  ┌─────────────────────────────────────────────────────────────┐
  │                         快排路径（默认）                     │
  │  常数因子小、缓存友好 ──── 大多数情况都走这条路               │
  └─────────────────────────────────────────────────────────────┘
                                    │
                    递归过深？──────┘
                        │
                        ▼
  ┌─────────────────────────────────────────────────────────────┐
  │                    堆排路径（保底）                          │
  │  最坏 O(n log n) ──── 仅在快排退化时触发                     │
  └─────────────────────────────────────────────────────────────┘
                                    │
                    小数组？────────┘
                        │
                        ▼
  ┌─────────────────────────────────────────────────────────────┐
  │                   插入排序路径（微观优化）                    │
  │  小数组常数极优 ──── n ≤ 16 时                               │
  └─────────────────────────────────────────────────────────────┘

7.3 在 Top-K 场景中，堆排序意外"获胜"

在某些 Top-K 场景中，堆的特点刚好使得堆成为唯一实用的选项：

  - 快排预处理: 需要 O(n) 额外空间（分区）→ 10 亿元素 = 4GB
  - Top-K 小顶堆: O(k) 空间 → k=1000 = 4KB

  k << n 时，Top-K 的根本优势是"不想也不需要排序全局数据"。
  堆只维护了"局部有序"（partial order），恰好满足需求。

  堆排序在这种场景中不是"被选为排序算法"，
  而是"堆作为数据结构"天生适合 Top-K 维护任务。

NOTE

本课不要求实现完整的堆排序，但理解堆排序与 Top-K 的关系很重要。堆排序的本质是：建堆 + n-1 轮交换调整。Top-K 中我们对堆做了类似的操作来排序输出——这其实就是堆排序的核心步骤在使用。

参考解答

练习1: heapify — 小顶堆向下调整

solution_39_heap_base_topk_heapify.c

#include <stdio.h>

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

/* 小顶堆下沉：让节点 i 向下调整至正确位置 */
void heapify(int arr[], int n, int i) {
    int smallest = i;          // 假设 i 是最小的
    int left  = 2 * i + 1;    // 左孩子索引
    int right = 2 * i + 2;    // 右孩子索引

    /* 找 i、left、right 三者中的最小值 */
    if (left  < n && arr[left]  < arr[smallest])
        smallest = left;
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    /* 如果最小值不是 i，交换并递归下沉 */
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

/* 测试 heapify 的 main */
int main(void) {
    int arr[] = {5, 1, 8, 3, 2};
    int n = 5;
    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    heapify(arr, n, 0);  // 调整根节点
    printf("After:  ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
/* 预期输出:
   Before: 5 1 8 3 2
   After:  1 2 8 3 5
*/

要点：先检查左右孩子索引是否越界（left < n, right < n），再比较值。找到最小值后与当前节点交换，并递归调整被交换的孩子位置。

练习2: build_heap — 自底向上建堆

solution_39_heap_base_topk_buildheap.c

#include <stdio.h>

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

void heapify(int arr[], int n, int i) {
    int smallest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] < arr[smallest]) smallest = l;
    if (r < n && arr[r] < arr[smallest]) smallest = r;
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

/* 建堆：从最后一个非叶节点开始，向前到 0 */
void build_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

int main(void) {
    int arr[] = {5, 3, 8, 1, 2};
    int n = 5;
    printf("Before: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");

    build_heap(arr, n);
    printf("After:  ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}
/* 预期输出:
   Before: 5 3 8 1 2
   After:  1 2 8 3 5
*/

要点：n/2 - 1 是最后一个非叶节点的索引（叶子节点无需调整）。自底向上确保在调用 heapify(i) 时，i 的子树已经是合法堆。

练习3: top_k — 完整 Top-K 实现

solution_39_heap_base_topk.c

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

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

/* 小顶堆下沉 */
void heapify(int arr[], int n, int i) {
    int smallest = i;
    int left  = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  < n && arr[left]  < arr[smallest])
        smallest = left;
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        heapify(arr, n, smallest);
    }
}

/* 建堆 */
void build_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

/* Top-K：输出 arr 中最大的 k 个（降序） */
void top_k(int arr[], int n, int k) {
    int *heap = malloc(k * sizeof(int));

    /* ① 将前 k 个元素拷入堆 */
    for (int i = 0; i < k; i++)
        heap[i] = arr[i];

    /* ② 建小顶堆 */
    build_heap(heap, k);

    /* ③ 遍历剩余元素：堆顶 = 门槛，比门槛大就替换 */
    for (int i = k; i < n; i++) {
        if (arr[i] > heap[0]) {
            heap[0] = arr[i];
            heapify(heap, k, 0);
        }
    }

    /* ④ 堆排序输出——将最小值交换到末尾，heapify 缩小范围 */
    for (int i = k - 1; i > 0; i--) {
        swap(&heap[0], &heap[i]);
        heapify(heap, i, 0);
    }

    /* ⑤ 从前往后打印（堆排序后已是降序：大→小） */
    for (int i = 0; i < k; i++) {
        printf("%d", heap[i]);
        if (i < k - 1) printf(" ");
    }
    printf("\n");

    free(heap);
}

int main(void) {
    char line1[1024], line2[32];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);

    int arr[1024], n = 0, k;

    char *tok = strtok(line1, " \n");
    while (tok) {
        arr[n++] = atoi(tok);
        tok = strtok(NULL, " \n");
    }

    sscanf(line2, "%d", &k);
    top_k(arr, n, k);
    return 0;
}

核心逻辑解析：

小顶堆维护"门槛"：heap[0] 始终是 K 个候选中的最小值。新元素只有大于这个门槛才有资格进入。这是整个 Top-K 的核心思想。
堆排序输出降序：将堆顶（最小值）与当前范围的最后一个元素交换，然后 heapify 缩小范围——这正是堆排序的核心步骤。完成后数组按降序排列，直接从前打印即可。
时间复杂度：build_heap O(k) + (n-k) 次 heapify × O(log k) = O(n log k)。当 k << n 时接近 O(n)。
空间复杂度：O(k)，仅需维护大小为 k 的堆。

对照检查：heapify 中检查了 left < n 和 right < n 吗？build_heap 从 n/2-1 逆向到 0 吗？top_k 中 arr[i] > heap[0] 的条件是"大于"（不是"小于"）吗？输出时 free(heap) 了吗？

课堂讨论

build_heap 从 n/2-1 开始逆向建堆——如果改成从 0 到 n-1 正向建堆，结果会怎样？什么情况下正向也可能"看起来成功"？
堆的数组表示中，(i-1)/2（父）和 2i+1/2i+2（子）的公式在 0-based 和 1-based 索引下有何不同？为什么 C 语言通常选择 0-based？
Top-K 算法中，为什么需要先用前 K 个元素建堆？能不能用一个空堆逐个插入？两者的复杂度有何区别？
假设你要在 1 亿条结构体记录中找"销售额最低的 10 个客户"——Customer 结构包含 ID、姓名、销售额。堆中存储什么？比较条件是什么？用什么堆？
heapify 的递归版本和迭代版本各自的适用场景是什么？在嵌入式系统上（栈空间仅 2KB），heapify 递归会不会出问题？
堆排序每次交换堆顶和末尾元素后执行 heapify——这和 Top-K 输出排序有什么异同？能否统一描述？

讨论答案

Q1: 正向建堆为什么不行？

正向建堆（从 0 到 n-1）违反了 heapify 的前提条件——heapify 假设孩子子树已经是合法堆。如果正向处理：

正向建堆: i=0, 1, 2, 3, 4

  i=0: heapify(0) → arr[1]子树未处理，不保证是堆 → 可能失败
  i=1: heapify(1) → 此时 arr[0]未正确调整 → 但 arr[0]可能 > arr[1]

什么情况下"看起来成功"？
  - 输入数组本身已接近堆序
  - 如果 heapify 写成了上滤（sift-up），正向反而"正确"
    （但这时操作本质不同了——是逐个插入，O(n log n)）

正向建堆与自底向上建堆的区别:
  正向: O(n log n)——每个节点都可能下沉/上滤到根
  逆向: O(n)——叶子一次不处理，底层节点只下沉1~2层

Q2: 0-based vs 1-based 索引的公式差异

0-based 索引（C 语言）:
  父: (i - 1) / 2
  左子: 2*i + 1
  右子: 2*i + 2

1-based 索引（《算法导论》等教材）:
  父: i / 2          （整数除法）
  左子: 2*i
  右子: 2*i + 1

为什么 C 选 0-based？
  1. 数组在 C 中从 0 开始——0-based 索引直接对应数组下标
  2. 地址计算: &arr[i] = base + i*sizeof(T), i=0 时就是 base
  3. 1-based 会浪费 arr[0] 这个位置

权衡:
  1-based 的公式更简洁（无 +1/-1）
  0-based 直接对应 C 数组地址，无需转换

实务中为省事通常选 0-based，
但你会在标准教材中看到 1-based 公式——
读论文/教材时注意换算！

Q3: 建堆 vs 逐个插入——复杂度对比

heap_build_vs_insert.c

/*
 * 方案 A: build_heap（本课方案）—— O(k)
 *   一次性把所有 K 个元素放入数组，自底向上 heapify
 */
void build_heap(int arr[], int k) {
    for (int i = k/2 - 1; i >= 0; i--)
        heapify(arr, k, i);
}

/*
 * 方案 B: 空堆逐个插入 —— O(k log k)
 *   从空堆开始，每次在末尾添加元素，向上调整（sift-up）
 */
void heap_push(int heap[], int *size, int val) {
    int i = (*size)++;
    heap[i] = val;
    // sift-up: 新元素向上浮
    while (i > 0 && heap[i] < heap[(i-1)/2]) {
        swap(&heap[i], &heap[(i-1)/2]);
        i = (i - 1) / 2;
    }
}

方案	时间复杂度	关键操作	适用场景
build_heap	O(k)	heapify 自底向上	已知所有元素
逐个插入	O(k log k)	每次 push sift-up	元素逐个到达
逐个插入 + Top-K	O(k log k + n log k)	——	元素逐个到达 + Top-K

对于 Top-K，build_heap 更优（已知前 K 个元素，可以批量建堆）。但如果元素是流式逐个到达（网络数据流），逐个插入是必须的。

Q4: 结构体 Top-K 的设计

struct_topk.c

// 客户结构体
struct Customer {
    int id;
    char name[32];
    double sales_amount;  // 销售额
};

/* 大顶堆 heapify——找最小的 K 个（堆顶 = K 个中最大值） */
void max_heapify_customer(struct Customer heap[], int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && heap[l].sales_amount > heap[largest].sales_amount)
        largest = l;
    if (r < n && heap[r].sales_amount > heap[largest].sales_amount)
        largest = r;
    if (largest != i) {
        /* swap heap[i] and heap[largest] */
        struct Customer tmp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = tmp;
        max_heapify_customer(heap, n, largest);
    }
}

核心答案：

堆中存储什么？ 完整的 Customer 结构体（或指向结构体的指针）。堆中的每个元素是一个客户记录。
比较条件？ 按 sales_amount 字段比较。"最低" = 最"小"——用大顶堆（堆顶 = K 个中销售额最高的 = 淘汰线）。
为什么是大顶堆？ 淘汰逻辑：新客户的销售额 < 堆顶（门槛）→ 新客户更低，置换掉最高的。堆顶就是 K 个候选中的"最高销售额"——刚好符合大顶堆定义。

Q5: 递归 vs 迭代 heapify 的安全性

递归 heapify 的调用栈深度 = 堆高 = O(log n)。对于 n=10^9（10 亿元素），log n ≈ 30。每个栈帧约 48 字节（返回地址 + 寄存器保存：x86-64），总计约 30 × 48 = 1440 字节 ≈ 1.4KB。

在 2KB 栈空间的嵌入式系统上：

如果堆中只有少量元素（如 n=1000, log n ≈ 10），递归安全
但 Top-K 下 k 很小（如 k=100, log k ≈ 7），递归完全安全
真正的风险是递归 depth 与堆高 h 的对数关系——log(∞) 增长极慢

安全建议：

通用库代码：用迭代版（避免任何栈溢出风险）
竞赛/评测：递归通常 OK（栈空间 8MB，远超需要）
嵌入式：计算最大深度 × 帧大小，确保 < 可用的空间

heapify_stack_safety.c

/* 递归 heapify 的栈帧大小估算 */
/*
 * x86-64 下粗略一帧:
 *   return address:    8 bytes
 *   saved rbp:         8 bytes
 *   local vars (i,l,r): 12 bytes
 *   alignment padding:  4 bytes
 *   ───────────────────────────
 *   total:            ~32 bytes
 *
 * 最大深度 30 → 30 × 32 = 960 bytes → 安全
 */

Q6: 堆排序与 Top-K 输出排序的异同

两者都使用"交换堆顶到末尾 + heapify 缩小范围"的固定模式，但目的不同：

heapsort_vs_topk.c

/*
 * 堆排序: 对整个数组排序（升序）
 * 建最大堆 → 逐次交换堆顶(最大值)到末尾 → 升序
 */
void heap_sort(int arr[], int n) {
    // 建最大堆（不是小顶堆！）
    for (int i = n/2-1; i >= 0; i--)
        max_heapify(arr, n, i);

    for (int i = n-1; i > 0; i--) {
        swap(&arr[0], &arr[i]);     // 最大值移到末尾
        max_heapify(arr, i, 0);
    }
    // 结果: arr 升序排列
}

/*
 * Top-K 输出排序: 只把堆中 K 个元素排序（等价于对小顶堆做"半个堆排序"）
 * 因为堆是小顶堆，交换最小值到末尾 → 数组变为升序 → 直接从前打印得降序
 */
void top_k_sort_and_print(int heap[], int k) {
    for (int i = k-1; i > 0; i--) {
        swap(&heap[0], &heap[i]);
        heapify(heap, i, 0);        // 注意: 小顶堆 heapify
    }
    // heap 现在升序 → 逆序打印得降序（最大的先输出）
}

统一视角：两者都利用了"堆顶是极值"的性质，反复取出极值放到末尾。区别在于：

堆排序：对全部 n 个元素排序，O(n log n)
Top-K 输出排序：只对K 个元素排序，O(k log k)，且 K << n

这也是"为什么 Top-K 不需要全局排序"的又一回答——你只需要弄清 K 个候选者的相对顺序，而不是全部 n 个元素。

课后练习

实现大顶堆版本。将 heapify 的比较条件反转（找最大而非最小），实现 max_heapify 和 max_build_heap。用大顶堆实现"找最小的 K 个数"，验证"找最小用大顶堆"的规则。

知识点提示：只需反转比较方向——arr[left] < arr[smallest] 改为 arr[left] > arr[largest]。找最小 K 个时，堆顶 = K 个中最大值 = 淘汰线。

参考解答

ex1_max_heap_topk.c

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

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

/* 大顶堆下沉：父 > 子 */
void max_heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        max_heapify(arr, n, largest);
    }
}

void max_build_heap(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--)
        max_heapify(arr, n, i);
}

/* 找最小的 k 个——用大顶堆 */
void min_k(int arr[], int n, int k) {
    int *heap = malloc(k * sizeof(int));
    for (int i = 0; i < k; i++) heap[i] = arr[i];
    max_build_heap(heap, k);  // 大顶堆初始

    for (int i = k; i < n; i++) {
        if (arr[i] < heap[0]) {  // 比门槛(最大值)小 → 有资格
            heap[0] = arr[i];
            max_heapify(heap, k, 0);
        }
    }

    /* 升序输出（从小到大） */
    for (int i = k-1; i > 0; i--) {
        swap(&heap[0], &heap[i]);
        max_heapify(heap, i, 0);
    }
    for (int i = 0; i < k; i++)
        printf("%d ", heap[i]);
    printf("\n");
    free(heap);
}

int main(void) {
    int arr[] = {5, 3, 8, 1, 9, 2};
    int n = 6;
    printf("最小的 3 个: ");
    min_k(arr, n, 3);  // 预期: 1 2 3
    return 0;
}

Top-K 频繁查询。如果数据不变但需要查询多个不同的 K 值（如先查 Top-3，再查 Top-10），每次重建堆效率低。设计一种方案减少重复计算。

知识点提示：一种方案是对数据排序 O(n log n)；另一种是用桶或分区思想——QuickSelect 分区可以 O(n) 找到第 K 大的数作为分界点。思考快排的 partition 如何在 Top-K 中发挥作用。

参考解答

ex2_quickselect_topk.c

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

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

/* QuickSelect: 找到第 k 大的元素（k from 0） */
int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {  // 升序
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[hi]);
    return i;
}

int quickselect(int arr[], int lo, int hi, int k) {
    if (lo == hi) return arr[lo];
    int p = partition(arr, lo, hi);
    if (p == k) return arr[p];
    if (p > k)  return quickselect(arr, lo, p-1, k);
    else        return quickselect(arr, p+1, hi, k);
}

/* 多次查询: 先找到分界点，再输出 */
void top_k_pass(int arr[], int n, int k) {
    // 找第 (n-k) 小的元素（分界点）
    quickselect(arr, 0, n-1, n-k);
    // 输出 arr[n-k..n-1]
    for (int i = n-k; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main(void) {
    int arr[] = {5, 3, 8, 1, 9, 2};
    int n = 6;
    int arr_copy[6];

    /* 多次查询——每次需要 copy */
    memcpy(arr_copy, arr, n * sizeof(int));
    top_k_pass(arr_copy, n, 3);  // 预期: 5 8 9

    memcpy(arr_copy, arr, n * sizeof(int));
    top_k_pass(arr_copy, n, 2);  // 预期: 8 9

    return 0;
}

堆合并。给定两个小顶堆（以数组表示，大小分别为 n 和 m），合并为一个合法小顶堆。是否可以在小于 O((n+m) log (n+m)) 的时间内完成？

知识点提示：将两个堆的所有元素放入新数组，然后 build_heap——O(n+m)。因为 build_heap 是 O(n) 而不是 O(n log n)。

参考解答

ex3_merge_heaps.c

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

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

void heapify(int arr[], int n, int i) {
    int smallest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] < arr[smallest]) smallest = l;
    if (r < n && arr[r] < arr[smallest]) smallest = r;
    if (smallest != i) { swap(&arr[i], &arr[smallest]); heapify(arr, n, smallest); }
}

void build_heap(int arr[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(arr, n, i);
}

/* 合并两个小顶堆——O(n+m) */
int* merge_heaps(int *h1, int n, int *h2, int m, int *total) {
    *total = n + m;
    int *merged = malloc((n + m) * sizeof(int));
    for (int i = 0; i < n; i++) merged[i] = h1[i];
    for (int i = 0; i < m; i++) merged[n + i] = h2[i];

    build_heap(merged, n + m);  // O(n+m), 不是 O((n+m)log(n+m))!
    return merged;
}

int main(void) {
    int h1[] = {1, 3, 5};  // 已是小顶堆
    int h2[] = {2, 4, 6};  // 已是小顶堆
    int total;
    int *h3 = merge_heaps(h1, 3, h2, 3, &total);

    printf("Merged heap: ");
    for (int i = 0; i < total; i++) printf("%d ", h3[i]);
    printf("\n");  // 预期: 1 2 5 3 4 6（合法小顶堆）
    free(h3);
    return 0;
}

关键洞察：如果以为合并两个堆需要一个个 pop/push（O((n+m)log(n+m))），就忽略了 build_heap 是 O(n+m) 的事实。直接 copy 数组再 build_heap 更高效。

流式 Top-K 模拟。修改 Top-K 主程序，不一次读取全部输入。每次从 stdin 读取一行，与堆顶比较，逐行处理。观察在不同 k 值下的缓冲区行为。

知识点提示：用 fgets + sscanf 逐行读取，避免调用 strtok 一次解析全部数据。重点是保持堆中始终只有 k 个元素。

参考解答

ex4_streaming_topk.c

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

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

void heapify(int arr[], int n, int i) {
    int smallest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] < arr[smallest]) smallest = l;
    if (r < n && arr[r] < arr[smallest]) smallest = r;
    if (smallest != i) { swap(&arr[i], &arr[smallest]); heapify(arr, n, smallest); }
}

int main(void) {
    char line[256];
    int k, val, count = 0;
    int *heap = NULL;

    /* 第一行: k 值 */
    fgets(line, sizeof(line), stdin);
    sscanf(line, "%d", &k);
    heap = malloc(k * sizeof(int));

    /* 逐行读取数据 */
    while (fgets(line, sizeof(line), stdin)) {
        if (sscanf(line, "%d", &val) != 1) break;

        if (count < k) {
            /* 积累阶段: 直接放入 */
            heap[count++] = val;
            if (count == k) {
                /* 满 k 个，建堆 */
                for (int i = k/2-1; i >= 0; i--)
                    heapify(heap, k, i);
            }
        } else {
            /* 流式处理: 只与堆顶比较 */
            if (val > heap[0]) {
                heap[0] = val;
                heapify(heap, k, 0);
            }
        }
    }

    /* 排序输出 */
    for (int i = k-1; i > 0; i--) {
        swap(&heap[0], &heap[i]);
        heapify(heap, i, 0);
    }
    for (int i = k-1; i >= 0; i--)
        printf("%d ", heap[i]);
    printf("\n");

    free(heap);
    return 0;
}

这个版本展示了流式 Top-K 的核心思想：任何时候内存中只有 k 个元素。数据可以来自文件、管道、网络流——对内存的影响完全相同。

堆判断函数。编写 int is_min_heap(int arr[], int n) 函数，判断一个数组是否满足小顶堆性质。遍历每个非叶节点，检查是否 ≤ 其孩子。

知识点提示：遍历索引 0 到 n/2-1，检查 arr[i] <= arr[2i+1] 和 arr[i] <= arr[2i+2]（注意边界）。这是 heap 性质的直接验证——不依赖 build_heap。

参考解答

ex5_is_min_heap.c

#include <stdio.h>

int is_min_heap(int arr[], int n) {
    for (int i = 0; i <= n/2 - 1; i++) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[i] > arr[left])
            return 0;  // 父 > 左子 → 违反小顶堆
        if (right < n && arr[i] > arr[right])
            return 0;  // 父 > 右子 → 违反小顶堆
    }
    return 1;  // 所有节点都满足堆性质
}

int main(void) {
    int h1[] = {1, 2, 3, 4, 5};  // 合法小顶堆
    int h2[] = {5, 1, 3, 4, 2};  // 不合法
    int h3[] = {1};               // 单元素（合法）
    int h4[] = {2, 1};            // 2 是单元素堆? 2 > 1 → 不合法

    printf("h1: %s\n", is_min_heap(h1, 5) ? "YES" : "NO");  // YES
    printf("h2: %s\n", is_min_heap(h2, 5) ? "YES" : "NO");  // NO
    printf("h3: %s\n", is_min_heap(h3, 1) ? "YES" : "NO");  // YES
    printf("h4: %s\n", is_min_heap(h4, 2) ? "YES" : "NO");  // NO
    return 0;
}

这个函数在调试堆实现时非常有用——每次操作后用 is_min_heap 验证堆性质是否被保持。

参考资料

《算法导论》(CLRS) 第 6 章 — 堆排序、建堆 O(n) 的严格分析、优先队列操作
《编程珠玑》(Programming Pearls) 第 11 章 — Top-K 海量数据实战与工程考量
《STL 源码剖析》(侯捷) 第 4 章 — C++ std::make_heap/std::sort 的 introsort 实现详解
VisuAlgo - Binary Heap — 堆操作的交互式动画演示，直观理解 heapify 过程
GeeksforGeeks - Introsort — 内省排序的结合策略与实现

"Make it work, make it right, make it fast." — Kent Beck

Lesson 39: 堆与 Top-K ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 完全二叉树与数组索引映射——堆的物理表示 ​

1.1 堆是一棵完全二叉树 ​

1.2 索引映射公式推导 ​

1.3 大顶堆 vs 小顶堆：两种堆序 ​

2. heapify——下滤（sift-down）的核心机制 ​

2.1 heapify 的前提条件 ​

2.2 小顶堆 heapify 完整逐步跟踪 ​

2.3 递归 vs 迭代：两种实现风格 ​

3. build_heap——建堆与 O(n) 复杂度的严格证明 ​

3.1 从 n/2-1 向上建堆的正确性 ​

3.2 O(n) 复杂度证明：Σ 收敛推导 ​

3.3 直观理解：为什么大多数节点几乎不下沉？ ​

4. Top-K 用小顶堆——核心洞察 ​

4.1 为什么是小顶堆？门槛直觉 ​

4.2 Top-K 算法逐步演示 ​

4.3 大顶堆为什么不行？ ​

5. "最大 K 用小堆"的阈值语义陷阱——面试必考 ​

5.1 陷阱：直觉与算法的冲突 ​

5.2 完整的对应关系表 ​

6. 流式 Top-K——O(k) 空间的工程价值 ​

6.1 问题场景：数据放不进内存 ​

6.2 流式 Top-K 实现 ​

7. 堆排序 vs 快速排序——最坏保证与缓存的权衡 ​

7.1 各自优劣分析 ​

7.2 introsort——取两者之长的智慧结合 ​

7.3 在 Top-K 场景中，堆排序意外"获胜" ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 39: 堆与 Top-K

练习任务

核心知识点

代码框架

深度讲解

1. 完全二叉树与数组索引映射——堆的物理表示

1.1 堆是一棵完全二叉树

1.2 索引映射公式推导

1.3 大顶堆 vs 小顶堆：两种堆序

2. heapify——下滤（sift-down）的核心机制

2.1 heapify 的前提条件

2.2 小顶堆 heapify 完整逐步跟踪

2.3 递归 vs 迭代：两种实现风格

3. build_heap——建堆与 O(n) 复杂度的严格证明

3.1 从 n/2-1 向上建堆的正确性

3.2 O(n) 复杂度证明：Σ 收敛推导

3.3 直观理解：为什么大多数节点几乎不下沉？

4. Top-K 用小顶堆——核心洞察

4.1 为什么是小顶堆？门槛直觉

4.2 Top-K 算法逐步演示

4.3 大顶堆为什么不行？

5. "最大 K 用小堆"的阈值语义陷阱——面试必考

5.1 陷阱：直觉与算法的冲突

5.2 完整的对应关系表

6. 流式 Top-K——O(k) 空间的工程价值

6.1 问题场景：数据放不进内存

6.2 流式 Top-K 实现

7. 堆排序 vs 快速排序——最坏保证与缓存的权衡

7.1 各自优劣分析

7.2 introsort——取两者之长的智慧结合

7.3 在 Top-K 场景中，堆排序意外"获胜"

参考解答

课堂讨论

讨论答案

课后练习

参考资料