小探险家学算法

Appearance

21. 插队王（堆） ​

知识点：堆（heap）—— 数组里住着一棵"永远最大在顶上"的树（取最大 O(1)，插入 O(log n)）

项目：游戏排行榜（随时知道第一名）+ 找出全班前 3 名

故事开场：第一名是谁？ ​

全班玩闯关游戏，每通关一次，老师就把新分数记下来。老师有个问题：

"现在谁是全班最高分？"

你翻了翻记录本——"这得从头看一遍，找最大的……"

老师每天都问！而且每次有新分数，都要重新找：

ts
const scores: number[] = []

// 新成绩进来
function addScore(score: number): void {
  scores.push(score)
}

// 找最高分：遍历一遍
function topScore(): number {
  let best = scores[0]
  for (let i = 1; i < scores.length; i++) {
    if (scores[i] > best) {
      best = scores[i]
    }
  }
  return best
}

你用第 10 章学的"找最大"写了个 topScore——每查一次，O(n)。

"50 个人，找一遍没问题。"老师说，"可要是全校 2000 人， 每次问第一名都要翻 2000 个分数？新成绩进来一个，第一名可能就变了， 又得重找？这也太笨了！"

笨办法先行：一直排着队？ ​

你灵机一动："那我每次加完分就排序！排好序，第一名就是最后一个！"

ts
function addScoreSorted(score: number): void {
  scores.push(score)
  scores.sort((a, b) => a - b)   // 每次加完分就排一次序
}

"不行不行，"你马上否定了自己，"每次加分都排序——加 n 次分、 排 n 次序，每次 O(n log n)，总共 O(n² log n)……为了一个'第一名'， 把整队都排一遍，太浪费了！"

你发现了问题的关键：我们只想要"最大的那个"，却每次都把全部数据折腾一遍。有没有一个结构，自动让最大的数待在"最顶上"， 随时一步取走？

引出知识点：堆——"最顶上永远最大"的树 ​

**堆（heap）**就是干这个的。它的思路很妙：用数组存一棵树。

想象一棵"树"，但有一个奇怪的规矩（大顶堆）：

每个节点都比它的孩子大（或相等）。

这条规矩保证了：根节点（最顶上）永远是全树最大的！

但堆最神奇的地方在于——它不用真的种树，用数组就能装！ 还记得数组的格子号吗？我们定一个规则：

下标 i 的节点的左孩子在 2i+1，右孩子在 2i+2，爸爸在 (i−1)÷2

比如下标 0（根）的孩子是 1 和 2；下标 1 的孩子是 3 和 4…… 数组里住着树，树住在数组里——这就是堆的"折叠空间"：

数组：[90, 70, 80, 50, 40, 30, 20]
       ↓
       90
      ↙    ↘
    70       80
   ↙  ↘    ↙  ↘
  50   40  30   20

看！90 > 70 和 80，70 > 50 和 40，80 > 30 和 20——每个都比孩子大。 所以根（数组第 0 个）一定是最大值：取最大 = 看数组第 0 个，O(1)！

动手实现：堆的"上浮"和"下沉" ​

插入新数（上浮）：新数先放到数组最后（树的"底部"）， 然后一路和爸爸比大小：比爸爸大？和爸爸换位，继续往上—— 直到爸爸比它大（或它到了顶）。像气泡一样往上浮：

ts
const heap: number[] = []      // 堆（大顶堆）：第 0 个永远最大

// 插入：新数放底部，一路"上浮"
function heapPush(value: number): void {
  heap.push(value)

  let i = heap.length - 1            // 新数的位置（数组最后）
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2)   // 爸爸的位置
    if (heap[parent] >= heap[i]) {
      break                          // 爸爸够大，不用换了
    }
    const temp = heap[parent]        // 新数比爸爸大？交换！
    heap[parent] = heap[i]
    heap[i] = temp
    i = parent                       // 继续往上浮
  }
}

const test = [70, 80, 30, 50, 40, 90, 20]
for (let i = 0; i < test.length; i++) {
  heapPush(test[i])
}
console.log(heap)

输出（第一项一定是最大的 90）：

[90, 80, 70, 50, 40, 30, 20]

看，90 一路浮到了顶上（第 0 位）！而且每个节点都比孩子大。

取走最大（下沉）：把顶上的最大数拿走，用最后一个数补到顶上， 然后一路和两个孩子比：哪个孩子大，就和哪个换，一路下沉：

ts
// 取出并拿走最大的数
function heapPopMax(): number {
  const top = heap[0]            // 最大的数（要返回它）

  const last = heap.pop()        // 拿走最后一个数
  if (last !== undefined && heap.length > 0) {
    heap[0] = last               // 最后一个数补到顶上

    let i = 0                    // 从顶上开始下沉
    while (true) {
      const left = i * 2 + 1     // 左孩子
      const right = i * 2 + 2    // 右孩子
      let biggest = i

      if (left < heap.length && heap[left] > heap[biggest]) {
        biggest = left
      }
      if (right < heap.length && heap[right] > heap[biggest]) {
        biggest = right
      }
      if (biggest === i) {
        break                    // 两个孩子都没自己大，沉到底了
      }
      const temp = heap[i]
      heap[i] = heap[biggest]
      heap[biggest] = temp
      i = biggest                // 继续下沉
    }
  }

  return top
}

跑起来：排行榜 ​

把堆装进排行榜：

ts
// 清空堆，重新来
heap.length = 0

// 全班成绩入堆
const scores = [78, 92, 65, 88, 70, 95, 60, 82]
for (let i = 0; i < scores.length; i++) {
  heapPush(scores[i])
}

console.log("现在最高分是：" + heap[0])   // 95，一步拿走！

// 新成绩进来
heapPush(99)
console.log("小明考了 99 分！现在最高分是：" + heap[0])   // 99！

// 第一名被'拿走'（比如被老师叫去领奖），下一位是谁？
console.log("领走第一名：" + heapPopMax())   // 99
console.log("新的最高分是：" + heap[0])      // 95

输出：

现在最高分是：95
小明考了 99 分！现在最高分是：99
领走第一名：99
新的最高分是：95

随时问、一步答——取最大 O(1)！插入一个新成绩， 最多往上浮 log n 层（树的高度），O(log n)。

对比一下：

办法查最高分加一个新成绩总共（加 n 个）
遍历找最大O(n)O(1)O(n²)
每次排序O(1)O(n log n)O(n² log n)
堆O(1)O(log n)O(n log n)

堆最擅长的事：不断有新数据进来、随时要"最大的"—— 游戏排行榜、电脑任务调度（谁优先级高先处理）、医院急诊分诊、 网络数据包排队……全是堆的天下。

小挑战 ​

  1. 前 3 名：反复调用 heapPopMax()，输出全班前 3 名的成绩。 想一想：为什么弹出 3 次就是前 3 名？（提示：每次都拿走最大的， 剩下的还是堆，下一个最大的自动浮在顶上。）
  2. 小顶堆：把堆反过来，变成"最小的在顶上"（提示：改两个 比较符号——>= 变 <=，找最小孩子时用 <。这就是小顶堆， 医院急诊用它：病情最重的先处理！）
  3. 堆排序：把 8 个成绩全部 heapPush 进堆，然后全部 heapPopMax() 弹出来——弹出的顺序是什么？这就是堆排序！ 它和选择排序像不像？（都是"每次挑最大的"，只是堆挑得特别快。）

课后练习 ​

第 1 题（动手题）：我的排行榜 ​

用堆做一个"得分排行榜"：依次插入 [45, 67, 89, 23, 90, 56]， 随时查询最高分；然后弹出第一名，再查询最高分；再插入一个 100， 再查询。每次查询用 heap[0] 一步搞定。

参考答案（点开查看）
ts
heap.length = 0
const list = [45, 67, 89, 23, 90, 56]
for (let i = 0; i < list.length; i++) {
  heapPush(list[i])
}

console.log(heap[0])        // 90
console.log(heapPopMax())   // 90（弹出第一名）
console.log(heap[0])        // 89
heapPush(100)
console.log(heap[0])        // 100

注意：heapPopMax 把最大数弹出后，剩下的依然是合法的堆—— 所以新最大（89）自动浮在顶上，不用重新整理。

第 2 题（思考题）：数组里的树 ​

为什么堆能用"数组存树"？想想下标公式： 左孩子 2i+1、右孩子 2i+2、爸爸 (i−1)÷2。 下标 3 的节点的爸爸是谁？孩子是谁？画一画验证。

参考答案（点开查看）

下标 3：爸爸是 (3−1)÷2 = 1；左孩子 2×3+1 = 7，右孩子 2×3+2 = 8。

画出来：

下标：0       1       2       3    4    5    6
      [90]   [80]   [70]   [50] [40] [30] [20]

下标 3 在树的第二层最左边（50），爸爸是下标 1（80）， 孩子是下标 7、8（如果在数组范围内的话）。

这个公式的妙处：数组的下标，直接告诉我们节点在树里的位置—— 不用真的造节点、不用存指针，妈妈再也不用担心我们丢钩子！

第 3 题（思考题）：堆 vs BST ​

堆和 BST 都是"数组/节点里住的树"。它们的区别是什么？ （提示：堆的规矩是"爸爸比孩子大"，BST 的规矩是"左小右大"。 中序遍历 BST 是排序——堆中序遍历是什么？）

参考答案（点开查看）
  • 堆的规矩：爸爸 ≥ 孩子。只管"最大在顶上"，不管左右谁大。 所以堆能 O(1) 取最大、O(log n) 插入；但它的左右子树是乱的—— 中序遍历堆不是排序！
  • BST 的规矩：左 < 根 < 右。能按顺序遍历、范围查询； 但取"最大"要一路往右走 O(log n)，没有 O(1) 的"顶上最大"。

一句话：堆是"抢第一"的专家（只知道最大）， BST 是"排顺序"的专家（全部有序）。各管一摊，谁也替代不了谁。

预告：进阶篇结束了！快速排序、归并排序、计数排序、二叉树、 二叉搜索树、堆——六件新武器入库！下一卷《高手篇》， 我们要玩真的了：迷宫寻路、爬楼梯、背包问题、地铁换乘…… 那些"听起来像数学竞赛"的难题，其实都有漂亮的套路。 准备好了吗？出发！