第9章 二叉堆最大堆

9.1 堆结构基础

9.1.1 堆结构的定义与分类

堆是一种基于完全二叉树实现的特殊树形数据结构，它通过严格的“堆序性质”来维持元素的偏序关系。堆可以进行很多分类，但是平时使用的基本都是二叉堆。

根据堆序性质的不同，二叉堆又可以划分为最大堆和最小堆：

（1）在最大堆中，每个节点的值都大于或等于其子节点的值，因此根节点存储着整个堆中的最大元素；

（2）在最小堆中，每个节点的值都小于或等于其子节点的值，根节点则存储着最小元素。这种结构仅要求父子节点之间满足大小关系，并不保证兄弟节点之间的有序性，因此它是一种“部分有序”的高效结构。

因此堆从表达形式上看是完全二叉树（除二叉树最后一层之外，其他各层节点数都达到最大个数，且最后一层的叶节点从左到右连续存在），但节点的排列顺序并不遵循二叉搜索树的规则（左子树所有节点的值都小于该节点值，右子树所有节点的值都大于该节点值，并且左右子树本身也要符合这一规则）。对于最大堆来说，子节点只需要比父节点来得小就行，而子节点是位于父节点的左子树还是右子树并没有硬性要求。

判断堆是最大堆还是最小堆只需要看根节点是整个节点的最大值还是最小值就可以。

图9-1 最大堆与最小堆

最大堆与最小堆如图9-1所示。

9.1.2 堆结构的应用场景

从堆结构的定义与分类来看，堆结构与完全二叉树好像属于强绑定的状态。如果不使用完全二叉树就不能实现堆结构吗？

不使用完全二叉树也是可以实现堆结构的，只需要将代码写好就行，但没人这么做。任何能够维护父子节点间特定大小关系（堆序性质）的树形结构都可以作为堆的底层实现。然而，完全二叉树之所以成为堆唯一被普遍采用的实现方式，是因为其与数组表示法的完美结合带来了不可替代的实践优势。这一点会在9.1.3小节中，通过堆的性质去了解。

那么，堆结构有什么意义吗？他存在的价值体现在哪里？对于每一个新的数据结构，我们都需要搞清楚为什么需要它，这是我们能够记住并且把握它的关键。它到底帮助我们解决了什么问题？

如果有一个集合（100，20，25，8，112），我们希望获取其中的最大值或者最小值，有哪些方案？该集合里的内容，人一眼就能看到最小值或者最大值在哪。可计算机程序不是人眼，没有办法一眼就看到，需要依据计算机的规则去做，例如需要遍历集合中的每个元素，通过比较操作来记录当前找到的最大值或最小值，这是在链表中所做的事情。

计算机获取集合中的最大值或者最小值常见的3个方法如下：

（1）数组/链表：遍历集合中的每个元素来比对，那获取最大或者最小值的开销是O(n)级别，可以排序，但我们只是获取最大值或者最小值而已，排序本身就很消耗性能。

（2）哈希表：不需要考虑，哈希表的元素存储是无序的，获取最值必须遍历所有元素进行比较，很难判断最大值最小值在哪个桶里。

（3）二叉搜索树：利用其有序性，最小值位于最左叶子节点，最大值位于最右叶子节点，通过从根节点沿单一方向查找即可在O(log n)平均时间内获得最值，但是二叉搜索树操作较为复杂，并且还要维护树的平衡时才是O(log n)级别。

这个时候需要一种数据结构来解决获取集合中的最大值或者最小值问题，即堆结构。

9.1.3 堆结构的性质与特点

堆结构通常是用来解决Top K问题的，Top K问题是一类常见的计算问题，其核心目标是从一个数量庞大（通常为N个）的数据集合中，高效地找出最靠前的K个具有某种极值特征的条目，这些条目可以是最大的K个数、最小的K个数、出现频率最高的K个词汇，或评分最高的K个项目等。

常用的解决方案有使用排序算法、快速选择算法、堆结构等等。Top K问题的关键挑战在于，当数据量N极大（例如数百万甚至数十亿）而K相对较小时，如果采用先完全排序再选取前K个的传统方法，其时间复杂度O(N log N)会带来巨大的计算开销。因此，Top K问题的核心在于寻找一种比完全排序更高效的算法策略，能够在仅遍历数据一到两遍、且维持一个较小内存空间（通常与K相关，而非N）的情况下，精准地筛选出所需的K个目标结果。

到目前为止，虽然我们通过堆结构的定义与分类，了解的堆结构的组成形态，但还不知道堆结构是如何实现的，以及二叉堆用树形结构表现时，具体长什么样子？

二叉堆用树形结构表现出来的是一棵完全二叉树，而二叉树实现的底层所使用的是数组。为什么二叉堆用树形结构所表现出来的会是一棵完全二叉树？而二叉树实现的底层为何又是数组？

在实现双向链表时，一个节点由prev，value以及next所组成，链表做法也是树的一种存储方式。在5.3小节中，有学习树的两种存储方式：数组存储与链表存储。因此回顾所学，可以得知在使用数组存储二叉树时，如果是完全二叉树，可以直接按照“从上到下、从左到右”的顺序依次放入数组下标中。这种方式简单高效且不会有空间浪费，因为完全二叉树不存在中间节点缺失的情况，节点之间的位置关系可以直接用数组下标计算得到（例如：下标 i 的左孩子是 2i，右孩子是 2i+1）。二叉堆的数组存储类似层序遍历，如图9-2所示。

图9-2 二叉堆-数组存储

如果二叉树的形态是完全二叉树，那么就可以利用数组的方式简单高效的实现存储。基于利用数组的角度，可以人为的将二叉堆往完全二叉树的方向塑造，而将二叉堆设置为完全二叉树的想法是可实现的。因此二叉堆用树形结构所表现出来的才会是完全二叉树。

由于完全二叉树存在极强且固定的顺序规律，因此每个节点在数组中对应的索引i（index）有如下4点规律总结：

（1）如果 i = 0 ，它是根节点。

（2）父节点的索引：floor( (i – 1) / 2 )。

（3）左子节点的索引：2i + 1。

（4）右子节点的索引：2i + 2。

如果二叉树的形态不是完全二叉树，那么想找到对应节点的索引虽然也可以做到，但复杂程度会直线上升，因此并不去考虑其他做法。

回到Top K问题上，找出最靠前的K个具有某种极值特征的条目，例如最大的3个数。由于二叉堆的完全二叉树并不要求左子节点一定比右子节点更大，如图9-2所示的数组索引2的值比索引1的值更大。所以只需要如下3步：

（1）提取根节点作为最大值。

（2）维护堆结构。

（3）重复3次。

这种方法确保了每次提取都是当前堆中的最大值，而每次维护堆结构并不会造成性能浪费。维护堆结构只是让替换上来的新根节点，沿着一条从根到叶子的单一路径，与较大的子节点进行比较和交换，这条路径的长度最多为树高，即 log₂n。每次调整只涉及树上的一条分支，而绝不会遍历或重组整棵树。

9.2 堆结构的实现

接下来，让我们对堆结构进行设计，看看需要有哪些属性和方法。

常见的属性：

（1）data：存储堆中的元素，通常使用数组来实现。

（2）size：堆中当前元素的数量。

常见的方法：

（1）insert(value)：在堆中插入一个新元素。

（2）extract/delete()：从堆中删除最大/最小元素。

（3）peek()：返回堆中的最大/最小元素。

（4）isEmpty()：判断堆是否为空。

（5）build_heap(list)：通过一个列表来构造堆。

较为陌生的有build_heap(list)方法，即通过一个列表来构造堆。其余4个方法涉及插入、删除、判空，查找等常规操作。从堆中删除最大/最小元素的常规方法名是delete，但由于堆结构的特殊性，例如Top K问题的提取当前堆中的最大值，则本质上当前堆的最大值就从二叉堆中删除了。因此提取最大值也有从堆中删除最大/最小元素的含义，extract的中文含义为"提取"。

那么接下来我们就来实现这个堆结构吧！

9.2.1 堆类的设计与封装

首先是封装Heap（堆）的类，整体封装思路流程与链表大致一致，将5个常见方法和2个属性初始化到Heap类中。

在堆结构中，节点之间交换是频繁的，因此创建私有工具方法swap，接收两个参数（节点内容位于数组中的位置，即索引），对传入的两个参数进行节点交换。交换节点是一个基础入门问题，A与B之间如何互换，有以下两种方式：

（1）创建临时变量C，A赋值C，B赋值A，C赋值B，实现A与B内容互换。

（2）解构赋值，[A,B] = [B,A]。

两种方式都可以，在之前有介绍过解构赋值的原理。

▼
ts
复制代码
class Heap<T> {
  // 属性
  private data: T[] = []
  private length: number = 0

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  // 方法
  insert(value: T) {}
  extract(): T | undefined {
    return undefined
  }

  peek(): T | undefined {

  }

  get size() {

  }

  isEmpty() {

  }

  buildHeap(arr: T[]) {

  }
}

export {}

我们接下来主要实现的是堆结构中如何插入新元素、如何删除最大/最小元素以及通过列表构造堆。以下的方法实现，都是以最大堆作为案例（最大堆会更常见一些）。

9.2.2 堆的插入操作与上浮

如果我们想实现一个最大堆，那么可以从实现insert()方法开始。因为堆结构一开始是空的，我们先往堆结构插入内容，一个有内容的堆去做查询，删除等操作才有意义。

在二叉堆（最大堆）中，堆必须始终满足一个核心不变式：任意父节点的值都不小于其子节点的值。而插入新元素时，为了保证结构仍然是一棵完全二叉树，新元素只能被放在数组末尾（即树的最底层、最右侧）。这个位置是由结构约束决定的，却并不保证数值关系是正确的，因此新插入的元素很可能比它的父节点更大，从而直接破坏最大堆的性质。如果不进行重构，后续的取最大值、删除堆顶等操作就会失去正确性。

为恢复最大堆性质，插入后需要执行向上调整（上浮，sift-up）：将新元素与其父节点比较，若新元素更大，则交换两者；交换后继续向上比较，直到它不再大于父节点，或已经成为堆顶为止。这个过程只沿着从插入位置到根节点的一条路径进行，时间复杂度为 O(log n)，却能在不破坏完全二叉树结构的前提下，高效地重新建立整个堆的有序性。这正是插入后必须进行堆重构的根本原因。

这很有意思，呼应了9.1.3小节中的Top K问题。总的来说，由于二叉堆（最大堆）的底层是数组存储，随意的将新元素插入到数组的任意位置会破坏完全二叉树（插入位置会导致后续元素全部后移一位），因此每次新元素只能先放到数组的最后面，先保证插入元素后，最大堆依旧是完全二叉树。在确定完全二叉树因素后，将插入元素与父节点不断比对，插入元素比父节点则两节点互换，然后重复比对互换操作，直到插入元素达到它应该到达的位置。从完全二叉树的形式看，插入元素在不断互换的过程，是一个攀升的过程，因此将其称为上浮。

现在来分析堆的插入操作是怎么样的，堆分2种情况：

（1）堆是空的。

（2）堆有元素。

不同情况的操作方式不同，如果堆是空的，那么插入的元素就直接push到data数组作为根节点。

如果堆有元素，需要按顺序操作以下3点步骤：

（1）将插入元素push到数组的尾部（保证堆处于完全二叉树状态）。

（2）将插入元素与父节点的大小比对，插入元素更大则执行swap()私有工具方法来交换节点。

（3）重复比对交换操作，直到插入元素上浮到对应位置（父节点大于插入元素或者插入元素到达根节点位置）。

步骤2与步骤3是为了保证堆符合最大堆的特性。插入元素上浮最多log₂n次，假设数组里有100万数据，那最多也就上浮20次，效率是很高的。在重复比对交换的过程中，一定要时刻更新插入元素所处的索引，每次元素比对交换过后，插入元素的索引都会发生变化，下一次上浮比对，无论是定位新的父节点还是插入元素的位置，都需要用到插入元素的新索引。

堆无论是空的还是有元素，都需要将插入元素push到数组尾部。堆有元素的情况，需要涉及到上浮操作。

▼
ts
复制代码
insert(value: T) {
  this.data.push(value)
  this.length++
  if (this.length > 1) {
    // 插入元素的位置
    let index = this.length - 1
    // 终止条件：上浮到根节点的位置
    while (index > 0) {
      const fatherIndex = Math.floor((index - 1) / 2)
      if (this.data[index] <= this.data[fatherIndex]) {
        break
      }
      this.swap(index, fatherIndex)
      index = fatherIndex
    }
  }
}

由于插入元素上浮在多处地方都可以使用到，因此单独封装一个heapify_up()上浮方法。this.length > 1的判断堆是否为空可加可不加，因为上浮操作中的循环判定条件index > 0已经完成相应判断。加上的可读性会更好一些。

▼
ts
复制代码
class Heap<T> {
  private data: T[] = []
  private length: number = 0

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  insert(value: T) {
    this.data.push(value)
    this.length++
    if (this.length > 1) this.heapify_up()
  }
  // 上浮操作
  private heapify_up() {
    // 插入元素的位置
    let index = this.length - 1
    // 终止条件：上浮到根节点的位置
    while (index > 0) {
      // 父节点位置
      const fatherIndex = Math.floor((index - 1) / 2)
      // 父节点大于插入元素
      if (this.data[index] <= this.data[fatherIndex]) {
        break
      }
      // 父节点小于插入元素 交换节点
      this.swap(index, fatherIndex)
      // 更新插入元素的最新索引
      index = fatherIndex
    }
  }
  
  HeapData() {
    console.log(this.data);
  }
  get size() {
    return this.length
  }
  extract() { }
  peek() { }
  isEmpty() { }
  build_heap() { }
}

const MaxHeap = new Heap<number>()
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
for (const item of arr) {
  MaxHeap.insert(item)
}
// 打印数组存储内容
MaxHeap.HeapData()

// 数组存储内容
// [
//   100, 19, 36, 17, 3,
//    25,  1,  2,  7
// ]

不同的插入顺序，所产生的完全二叉树不一定完全相同，只能确保最大值是一致，而我们需要关心的也只有最大值（数组中的第一个值）。

9.2.3 可视化网站推荐

虽然最大堆最需要关心的最大值位置可以从数组中很快速的看到。但有些时候，我们也想看最大堆的整体树形结构中，是如何按照从大到小逐层排列以及插入元素是如何一步步上浮的。在实现堆的其余方法后，也可以利用可视化网站来查看堆的常见方法的可视化上浮或下沉过程。

网站1：Binary Heap (Priority Queue) - VisuAlgo。

网站2：Data Structure Visualization PS：加利福尼亚州的旧金山大学提供。

假如我们现在有一个如图9-3所示的最大堆，要插入120，其中的变化过程是怎么样的。有可视化的树形动画效果可以直观的感受，降低学习难度，但过度依赖可视化就有可能出现不使用该可视化就写不出来代码的情况。

图9-3 最大堆-插入元素insert

9.2.4 堆的删除操作与下沉

删除操作也需要考虑在删除元素后的操作，因为每次删除元素后，堆结构会空出一个位置，如果删除的元素不是最后一个元素，就会破坏堆的完全二叉树结构，需要对堆进行重构，以维护最大堆的性质。

如果在堆中直接删除某个位置的元素（尤其是堆顶或中间节点），并试图让其子节点沿着路径逐层“向前、向上填补空位”，那么这一做法会带来两个严重问题：第一，填补路径并不唯一，需要在左右子树之间反复选择，逻辑复杂且容易出错；第二，每次填补都会改变多个节点的父子关系，很可能在填补过程中多次破坏最大堆性质，从而不得不在多个方向上反复调整，整体实现复杂且难以保证效率。

正规的做法是采用“末尾元素替换 + 下沉（sift-down）”策略：先用数组最后一个元素替换被删除的元素位置（通常是堆顶），再删除数组末尾，从而一次性恢复完全二叉树结构。此时，唯一可能被破坏的只是新放上来的这个元素与其子节点之间的大小关系，于是只需让它沿着一条路径向下与更大的子节点交换，直到满足最大堆性质为止。让末尾元素填补被删除的空缺位置，做到了只有一个元素不符合最大堆，最小程度的破坏最大堆的特性。这样，结构修复是 O(1)，有序性修复是 O(log n)，既避免了路径级联填补的复杂性，又保证了堆操作的高效与可控性。

在实现二叉堆（最大堆）的删除操作时，可以将逻辑清晰地划分为两种情况：

（1）删除的元素本身就是堆的最后一个元素（即位于最后一层最右侧的叶子节点，对应数组的末尾）。此时直接删除该元素即可，既不会破坏完全二叉树的结构，也不会影响最大堆的性质，无需进行任何额外调整。

（2）删除的元素位于除上述位置以外的任意节点。这时若直接删除，会在堆中间留下“空洞”，从而破坏完全二叉树结构。正确的做法是：先将该元素与数组末尾的元素交换位置，再删除数组末尾的元素。这样可以在 O(1) 的时间内恢复完全二叉树结构。随后，只需针对被交换上来的这个元素执行堆的重构（根据其与父节点或子节点的大小关系，进行下沉或必要时的上浮），使其回到正确的位置，从而重新维护最大堆的性质。

堆的删除操作与元素下沉如图9-4所示。

图9-4 堆的删除操作

最大堆的删除操作有很多种，在代码上的表现形式也不同，常见的有以下3种：

（1）可以先将该元素与数组末尾的元素交换位置，再删除数组末尾的元素。

（2）直接用数组末尾的元素覆盖在被删除元素的位置上，然后删除数组末尾元素。

（3）使用Array.prototype.pop()实例方法将数组末尾元素删除，并将删除的末尾元素赋值到被删除元素位置。

无论哪种删除操作，最终都需要完成元素下沉操作。

最大堆的元素个数为0或者为1的代码如下：

▼
ts
复制代码
extract(): T | undefined {
  if (this.length === 0) return undefined
  if (this.length === 1) {
    this.length--
    return this.data.pop()
  }
}

当最大堆的元素个数大于1的情况，需要使用到下沉操作，下沉操作与插入方法中的上浮操作类似，因此我们将下沉操作也单独封装为一个私有方法heapify_down，最后在extract()方法中使用。

将目标元素下沉，需要获取目标元素的左子节点和右子节点。对比左右子节点的大小，获取值较大的子节点，将该子节点与目标节点的值进行比较，若目标节点的值更小，则交换节点位置，反之则终止下沉。交换完位置，需要更新目标元素的索引，然后重复以上交换操作，最终令目标元素下沉到对应位置（下沉范围需要在二叉树范围，超出范围则终止下沉），完成最大堆重构。

▼
ts
复制代码
private heapify_down() {
  // 3.1.定义索引位置
  let index = 0

  while (2 * index + 1 < this.length) {
    // 3.2.找到左右子节点
    let leftChildIndex = 2 * index + 1
    let rightChildIndex = leftChildIndex + 1

    // 3.3.找到左右子节点较大的值
    let largerIndex = leftChildIndex
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 3.4.较大的值和index位置进行比较
    if (this.data[index] >= this.data[largerIndex]) {
      break
    }

    // 3.5.交换位置
    this.swap(index, largerIndex)
    index = largerIndex
  }
}

最后，回到extract()方法中完成最大堆删除操作中的情况2，实现下沉操作的同时，将提取的最大值返回出去。

▼
ts
复制代码
/** 提取操作 */
extract(): T | undefined {
  // 1.判断元素的个数为0或者1的情况
  if (this.length === 0) return undefined
  if (this.length === 1) {
    this.length--
    return this.data.pop()!
  }

  // 2.提取并且需要返回的最大值
  const topValue = this.data[0]
  this.data[0] = this.data.pop()!
  this.length--

  // 3.维护最大堆的特性: 下滤操作
  this.heapify_down()

  return topValue
}

测试用例如下：

▼
ts
复制代码
const MaxHeap = new Heap<number>()
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
for (const item of arr) {
  MaxHeap.insert(item)
}
MaxHeap.extract()
// 打印数组存储内容
MaxHeap.HeapData()
// 删除前
// [
//   100, 19, 36, 17, 3,
//    25,  1,  2,  7
// ]
// 删除后
// [
//   36, 19, 25, 17,
//    3,  7,  1,  2
// ]

9.2.5 堆的其他操作方法

在实现堆结构的初始化搭建中，有3个较为简单的操作方法，分别是：

（1）peek()方法获取最大最小值，即根节点的位置（数组存储，数组的第一个元素）。

（2）size()属性方法获取堆结构长度（数组存储，所以获取的是数组的长度）。

（3）isEmpty()方法判断堆结构是否为空（数组存储，所以判断数组长度是否为0）。

▼
ts
复制代码
  peek(): T | undefined {
    return this.data[0]
  }

  get size() {
    return this.length
  }

  isEmpty() {
    return this.length === 0
  }

9.3 堆的高级应用

9.3.1 原地建堆算法

原地建堆（In-place heap construction）是指在将一个无序数组转换为堆（如最大堆或最小堆）时，不借助任何额外的数据结构或辅助数组，而是直接在原数组本身上通过元素交换与调整完成建堆过程。

我们之前的建堆方式是将无序数组通过for of遍历出单独的元素，将单独的元素插入到另一个存储堆结构的数组中，每一次插入都会触发上浮操作，使存储堆结构的数组始终能够保持最大堆的性质。

▼
ts
复制代码
const MaxHeap = new Heap<number>()
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
for (const item of arr) {
  MaxHeap.insert(item)
}

上述的建堆方式，将建堆与初始化拆解成两部分，即初始化的最大堆一定是空的。插入元素与"建堆"的含义过于绑定在一起。

有时候，希望将建堆与插入元素在做法上区分开，从方法的使用上将原地建堆与插入元素拆分，可以避免功能上的混淆。如下代码示例。

▼
ts
复制代码
// 初始化最大堆的同时，完成原地建堆
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
const MaxHeap = new Heap<number>()
// 原地建堆
MaxHeap.buildHeap(arr)

可原地建堆所调用的buildHeap()方法从使用角度来看，基本上只需要使用一次，后续对堆结构的变动只需要在原有基础上去修修改改。那么我们希望在初始化最大堆的实例对象时，就能够同时完成建堆的操作，将buildHeap()方法与初始化堆结合在一起，如下代码示例。

▼
ts
复制代码
// 初始化最大堆的同时，完成原地建堆
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
const MaxHeap = new Heap<number>(arr)

将buildHeap()方法与初始化堆结合在一起，要如何去做？可以通过如下3步骤：

（1）在创建 Heap 类实例（如 MaxHeap）时，将数组 arr 作为构造参数传入构造函数，用于初始化实例内部的数据存储。

（2）构造函数在完成基础初始化后，调用实例方法 buildHeap()，在原数组上执行原地建堆操作，将无序数组调整为满足最大堆性质的结构。

（3）建堆完成后，堆结构由该实例对象持有并维护，后续的插入、删除等操作均基于这一已建好的堆进行。

那么梳理清楚思路后，来完成代码的编写，首先完成基础框架的初始化，将数组 arr 作为构造参数传入构造函数，并调用实例方法buildHeap()来完成原地建堆。当开发者未传入数组arr，则数组arr是空的，长度为0，那么无需原地建堆，做好边界判断。

▼
ts
复制代码
class Heap<T> {
  // 属性
  data: T[] = []
  private length: number = 0
  // 省略其余暂时用不到的代码部分
  constructor(arr: T[] = []) {
    if (arr.length === 0) return
    this.buildHeap(arr)
  }

  buildHeap(arr: T[]) {

  }
}
const arr = [9, 11, 20, 56, 23, 45]
const heap = new Heap<number>(arr)

根据如上原地建堆的基础框架，主要需要实现的是实例方法buildHeap()。目前实例方法buildHeap()通过参数传递的方式已经拿到无序数组arr，将无序数组转换成堆结构的数组存储，必然是需要使用到上浮或者下沉操作的。

原地建堆操作是直接在原数组本身上通过元素交换与调整完成建堆过程，因此需要用尽可能少的交换次数来完成建堆。

那么在原地建堆中，上浮与下沉哪一种方式的效率更高？在原地建堆（buildHeap）里，用“下沉（sift-down）”的方式效率更高，也是标准做法；而用“上浮（sift-up）”逐个插入虽然也能建成堆，但整体更慢。原因如下：

• 上浮建堆相当于把数组元素一个个当作“插入操作”塞进堆里：每插入一个元素，最坏要上浮到根，代价是 O(log n)；做 n 次就是 O(n log n)。

• 下沉建堆是从最后一个非叶子节点开始，逐个对节点做下沉，让每棵子树先变成堆：靠近底部的节点高度很小，下沉距离短，只有少数靠近根的节点才可能下沉较多，因此总成本被摊薄，整体是 O(n)。最后一个非叶子节点如图9-5所示。

图9-5 最后一个非叶子节点

在原地建堆中采用下沉（sift-down）的方式，是因为虽然需要对多个节点执行下沉操作，但绝大多数节点位于完全二叉树的底部附近。这些节点下面的层数很少，哪怕发生下沉，最多也只需移动一两步，甚至完全不需要移动；真正可能下沉较多的，只有极少数靠近根节点的元素。由于节点数量随着层级向上迅速减少，能下沉很多层的节点数量非常少，而数量最多的节点几乎不消耗调整成本。把“节点数量 × 每个节点的最大下沉距离”加在一起，整体开销被平均（摊薄）下来后，只与元素个数成正比，因此自底向上的下沉建堆时间复杂度为 O(n)，而不是 O(n log n)。

以上是从数据分析的角度去理解，而在做决策时，我们可以从逻辑方面去分析：

最大堆呈上窄下宽的金字塔形状，绝大多数元素都在底部。最大堆的底部元素的下沉次数少（最多也就一两层就到最底部了），因此减少最多元素部分的交换次数，是最能有效减少最大堆整体元素交换次数的关键。下沉操作在这方面比上浮更具备优势。

代码编写思路如下3步：

（1）获取最后一个非叶子节点（最后一个节点的父节点），固定公式floor( (i – 1) / 2 )。

（2）堆结构从最后一个非叶子节点往上层按顺序一个个去比对元素大小（比对到根元素为止结束），完成下沉操作，实现最大堆的性质。

▼
ts
复制代码
buildHeap(arr: T[]) {
  // 1.使用arr的值: 数组/长度
  this.data = arr
  this.length = arr.length

  // 2.从第一个非叶子节点, 开始进行下滤操作
  const start = Math.floor(this.length / 2 - 1)
  for (let i = start; i >= 0; i--) {
    this.heapify_down(i)
  }
}

由于实例方法heapify_down()的下沉操作，在之前是固定从根节点作为初始索引，为了配合特定位置的元素下沉，需要做出一点修改，支持传入索引参数作为初始索引。

▼
ts
复制代码
private heapify_down(start: number) {
  // 3.1.定义索引位置
  let index = start

  while (2 * index + 1 < this.length) {
    // 3.2.找到左右子节点
    let leftChildIndex = 2 * index + 1
    let rightChildIndex = leftChildIndex + 1

    // 3.3.找到左右子节点较大的值
    let largerIndex = leftChildIndex
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 3.4.较大的值和index位置进行比较
    if (this.data[index] >= this.data[largerIndex]) {
      break
    }

    // 3.5.交换位置
    this.swap(index, largerIndex)
    index = largerIndex
  }
}

最大堆到目前为止，完整的代码示例如下：

▼
ts
复制代码
class Heap<T> {
  private data: T[] = []
  private length: number = 0

  constructor(arr: T[] = []) {
    if (arr.length === 0) return
    this.buildHeap(arr)
  }

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  insert(value: T) {
    this.data.push(value)
    this.length++
    if (this.length > 1) this.heapify_up()
  }
  // 上浮操作
  private heapify_up() {
    // 插入元素的位置
    let index = this.length - 1
    // 终止条件：上浮到根节点的位置
    while (index > 0) {
      // 父节点位置
      const fatherIndex = Math.floor((index - 1) / 2)
      // 父节点大于插入元素
      if (this.data[index] <= this.data[fatherIndex]) {
        break
      }
      // 父节点小于插入元素 交换节点
      this.swap(index, fatherIndex)
      // 更新插入元素的最新索引
      index = fatherIndex
    }
  }

  HeapData() {
    console.log(this.data);
  }
  /** 提取操作 */
  extract(): T | undefined {
    // 1.判断元素的个数为0或者1的情况
    if (this.length === 0) return undefined
    if (this.length === 1) {
      this.length--
      return this.data.pop()!
    }

    // 2.提取并且需要返回的最大值
    const topValue = this.data[0]
    this.data[0] = this.data.pop()!
    this.length--

    // 3.维护最大堆的特性: 下滤操作
    this.heapify_down()

    return topValue
  }
  private heapify_down(start: number) {
    // 3.1.定义索引位置
    let index = start

    while (2 * index + 1 < this.length) {
      // 3.2.找到左右子节点
      let leftChildIndex = 2 * index + 1
      let rightChildIndex = leftChildIndex + 1

      // 3.3.找到左右子节点较大的值
      let largerIndex = leftChildIndex
      if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
        largerIndex = rightChildIndex
      }

      // 3.4.较大的值和index位置进行比较
      if (this.data[index] >= this.data[largerIndex]) {
        break
      }

      // 3.5.交换位置
      this.swap(index, largerIndex)
      index = largerIndex
    }
  }
  get size() {
    return this.length
  }
  peek(): T | undefined {
    return this.data[0]
  }

  isEmpty() {
    return this.length === 0
  }
  buildHeap(arr: T[]) {
    // 1.使用arr的值: 数组/长度
    this.data = arr
    this.length = arr.length

    // 2.从第一个非叶子节点, 开始进行下滤操作
    const start = Math.floor(this.length / 2 - 1)
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i)
    }
  }
}

const MaxHeap = new Heap<number>()
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
for (const item of arr) {
  MaxHeap.insert(item)
}
MaxHeap.extract()
// 打印数组存储内容
MaxHeap.HeapData()

9.3.2 最小堆（原地建堆）

在9.3.1小节中，实现了最大堆的原地建堆。而最小堆的原地建堆是类似的原理，只需要修改维护最大堆的私有工具方法heapify_up()的一部分代码就可以实现最小堆的原地建堆。

私有工具方法heapify_up()中的this.data[index]需要大于等于this.data[parentIndex]，即子节点比父节点大的时候，终止元素交换，在这种交换规则下，堆结构就会呈现上小下大的布局分层，而根节点则会是最小值。

▼
ts
复制代码
private heapify_up() {
  let index = this.length - 1
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2)
    // 最小堆的比对修改
    if (this.data[index] >= this.data[parentIndex]) {
      break
    }
    this.swap(index, parentIndex)
    index = parentIndex
  }
}

完成私有工具方法heapify_up()的修改，可以通过for of遍历无序数组的方式，将二叉堆的性质转变为最小堆。

▼
ts
复制代码
const arr = [19, 100, 36, 17, 3, 25]
// 最小堆测试插入操作
// const heap = new Heap<number>()
// for (const item of arr) {
//   heap.insert(item)
// }

但此时最小堆在私有工具方法heapify_down()进行删除操作时，就会出现问题。原代码如下：

▼
ts
复制代码
private heapify_down(start: number) {
  // 3.1.定义索引位置
  let index = start

  while (2 * index + 1 < this.length) {
    // 3.2.找到左右子节点
    let leftChildIndex = 2 * index + 1
    let rightChildIndex = leftChildIndex + 1

    // 3.3.找到左右子节点较大的值
    let largerIndex = leftChildIndex
    if (rightChildIndex < this.length && this.data[rightChildIndex] > this.data[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 3.4.较大的值和index位置进行比较
    if (this.data[index] >= this.data[largerIndex]) {
      break
    }

    // 3.5.交换位置
    this.swap(index, largerIndex)
    index = largerIndex
  }
}

修改私有工具方法heapify_down()，使其适用于最小堆：

（1）this.data[rightChildIndex] < this.data[leftChildIndex]：寻找左右子节点中，更小的值。

（2）this.data[index] <= this.data[largerIndex]：父节点如果小于左右子节点中更小的那个节点，则终止节点交换（下沉）。

▼
ts
复制代码
private heapify_down(start: number) {
  // 省略无变动代码
  let largerIndex = leftChildIndex
  if (rightChildIndex < this.length && this.data[rightChildIndex] < this.data[leftChildIndex]) {
    largerIndex = rightChildIndex
  }
  if (this.data[index] <= this.data[largerIndex]) {
    break
  }
  // 省略无变动代码
}

测试最小堆的提取方法extract()，所导致的删除节点可正常执行。

▼
ts
复制代码
// 2.测试提取/删除操作
while (!heap.isEmpty()) {
  console.log(heap.extract())
}

由于批量建堆使用到的是下沉操作，而在测试最小堆的提取方法extract()时，已修改下沉操作，因此最小堆的批量建堆可以直接使用。

▼
ts
复制代码
// 3.测试批量建堆
const heap = new Heap<number>(arr)
console.log(arr)
console.log(heap.extract())

9.3.3 最大堆与最小堆的合并

如果我想将最大堆与最小堆合并在一个类中，能不能做到？

当然是可以的，最大堆和最小堆的区别只在于3个地方的大小比对上相反而已：

（1）维护最大堆或者最小堆结构的实例方法heapify_up()，有一处地方。

（2）下沉操作的实例方法heapify_down()，有两处地方。

在3处地方，加上判断走最大堆或者最小堆的逻辑（在实例化对象时，额外传入布尔值用于控制当前实例对象是要走最大堆还是最小堆的逻辑），修改一下比对形式以及元素交换条件，就可以完成最大堆与最小堆的合并。

默认走最大堆逻辑，当布尔值为false时，走最小堆逻辑。

▼
ts
复制代码
export default class Heap<T> {
  // 属性
  private data: T[] = []
  private length: number = 0
  private isMax: boolean

  constructor(arr: T[] = [], isMax = true) {
    this.isMax = isMax
    if (arr.length === 0) return
    this.buildHeap(arr)
  }
}
// 3.测试批量建堆
const heap = new Heap<number>(arr, false)

然后对最大堆与最小堆有差异的三处地方，做出封装和判断，封装出私有工具方法compare()，通过传入两个索引，用于判断走最大堆或者最小堆的逻辑，最后返回布尔值。PS：因为最大堆与最小堆有差异的三处地方都是通过索引，判断子节点与父节点之间是否要交换。所以私有工具方法compare()只需要通过子节点与父节点的索引还有最大/小堆的判断，就可以实现父子节点之间是否要交换位置的判断。

▼
ts
复制代码
private compare(i: number, j: number): boolean {
  if (this.isMax) {
    return this.data[i] >= this.data[j]
  } else {
    return this.data[i] <= this.data[j]
  }
}

使用私有工具方法compare()的三处地方如下，完成二叉堆（最大堆与最小堆）类的实现。通过复制最大堆的完整代码，添加isMax属性和构造函数中实现赋值，替换掉以下两个私有工具方法heapify_up()和heapify_down()以及添加私有工具方法compare()即可完成二叉堆的重构。

总结：对3个私有方法的重构。

▼
ts
复制代码
private heapify_up() {
  let index = this.length - 1
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2)
    // 位置一
    if (this.compare(parentIndex, index)) {
      break
    }
    this.swap(index, parentIndex)
    index = parentIndex
  }
}

private heapify_down(start: number) {
  let index = start
  while (2 * index + 1 < this.length) {
    let leftChildIndex = 2 * index + 1
    let rightChildIndex = leftChildIndex + 1
    let largerIndex = leftChildIndex
    // 位置二
    if (rightChildIndex < this.length && this.compare(rightChildIndex, leftChildIndex)) {
      largerIndex = rightChildIndex
    }
    // 位置三
    if (this.compare(index, largerIndex)) {
      break
    }
    this.swap(index, largerIndex)
    index = largerIndex
  }
}

9.3.4 二叉堆的打印

在前面无论是最大堆还是最小堆的打印，都是以数组的形式去展现的，并不能够直观的展现我们最大堆/最小堆的二叉树可视化展示效果。9.2.3小节的可视化网站是可视化的固定输入效果，适合理解数据结构的运行过程，但不能看出我们实际代码运行的效果。

因此可以安装第三方库hy-algokit，用于在控制台可视化打印输出效果。

▼
ts
复制代码
pnpm i hy-algokit

使用方式如下：

▼
ts
复制代码
import { cbtPrint } from 'hy-algokit'

// 在二叉堆类中实现以下方法
print() {
    cbtPrint(this.data)
}

完成二叉堆的可视化打印：

▼
ts
复制代码
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
const MaxHeap = new Heap<number>(arr, false)

console.log(arr)
cbtPrint(arr)
console.log(MaxHeap.extract())

MaxHeap.print()

二叉堆可视化打印如图9-6所示。

图9-6 二叉堆可视化打印

二叉堆完整代码如下：

▼
ts
复制代码
import { cbtPrint } from 'hy-algokit'
class Heap<T> {
  private data: T[] = []
  private length: number = 0
  private isMax: boolean

  constructor(arr: T[] = [], isMax = true) {
    this.isMax = isMax
    if (arr.length === 0) return
    this.buildHeap(arr)
  }

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  insert(value: T) {
    this.data.push(value)
    this.length++
    if (this.length > 1) this.heapify_up()
  }
  // 上浮操作
  private heapify_up() {
    let index = this.length - 1
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2)
      // 位置一
      if (this.compare(parentIndex, index)) {
        break
      }
      this.swap(index, parentIndex)
      index = parentIndex
    }
  }
  private compare(i: number, j: number): boolean {
    if (this.isMax) {
      return this.data[i] >= this.data[j]
    } else {
      return this.data[i] <= this.data[j]
    }
  }
  private heapify_down(start: number) {
    let index = start
    while (2 * index + 1 < this.length) {
      let leftChildIndex = 2 * index + 1
      let rightChildIndex = leftChildIndex + 1
      let largerIndex = leftChildIndex
      // 位置二
      if (rightChildIndex < this.length && this.compare(rightChildIndex, leftChildIndex)) {
        largerIndex = rightChildIndex
      }
      // 位置三
      if (this.compare(index, largerIndex)) {
        break
      }
      this.swap(index, largerIndex)
      index = largerIndex
    }
  }

  HeapData() {
    console.log(this.data);
  }
  /** 提取操作 */
  extract(): T | undefined {
    // 1.判断元素的个数为0或者1的情况
    if (this.length === 0) return undefined
    if (this.length === 1) {
      this.length--
      return this.data.pop()!
    }

    // 2.提取并且需要返回的最大值
    const topValue = this.data[0]
    this.data[0] = this.data.pop()!
    this.length--

    // 3.维护最大堆的特性: 下滤操作
    this.heapify_down(0)

    return topValue
  }
  get size() {
    return this.length
  }
  peek(): T | undefined {
    return this.data[0]
  }

  isEmpty() {
    return this.length === 0
  }
  buildHeap(arr: T[]) {
    // 1.使用arr的值: 数组/长度
    this.data = arr
    this.length = arr.length

    // 2.从第一个非叶子节点, 开始进行下滤操作
    const start = Math.floor(this.length / 2 - 1)
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i)
    }
  }
  print() {
    cbtPrint(this.data)
  }
}
// 测试用例
const arr = [19, 100, 36, 17, 3, 25, 1, 2, 7]
const MaxHeap = new Heap<number>(arr, false)

console.log(arr)
cbtPrint(arr)
console.log(MaxHeap.extract())

MaxHeap.print()