二叉堆

备注

该部分是补充部分知识，用于介绍二叉堆排序，在调用程序中被用作创建有序的 taskQueue （任务）和 timerQueue （延迟）列队。

信息

若对该部分知识比较熟悉可跳过忽略

堆（ Heap ）是一个能 快速拿到最大/最小值 、并 高效插入新元素 的数据结构。首先出现在 1964 年 J.W.J.Williams 在论文 “Algorithm 232: Heapsort“ 中，作为 **堆排序（Heapsort）算法的一部分。是用于早期 **伪代码或汇编/早期 Fortran** 描述。

一、二叉堆

堆是一颗 完全二叉树 ，但不用真的建树，而是用数组储存。

完全二叉树 ：用数组紧凑储存，无空洞
堆性质 ：
- 最小堆：父节点 ≤ 子节点（根是最小值）
- 最大堆：父节点 ≥ 子节点（根是最大值）

二、实现（最小堆）

class MinHeap<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;

  constructor(compareFn?: (a: T, b: T) => number) {
    // 默认为数字最小堆
    this.compare = compareFn ?? ((a, b) => (a as any) - (b as any));
  }
  // 二叉堆的长度
  size(): number {
    return this.heap.length;
  }
  // 二叉堆是否为空
  isEmpty(): boolean {
    return this.size() === 0;
  }
  // 查看最小值，但不移除
  // 时间复杂度：O(1) （直接取数组第一个元素）
  peek(): T | undefined {
    return this.heap[0];
  }

  push(value: T): void {
    this.heap.push(value); // 先放到最后
    this.siftUp(this.heap.length - 1); // 再“上浮”到正确位置
  }
  // 去除最小值
  pop(): T | undefined {
    if (this.isEmpty()) return undefined;
    // 保存最小值
    const top = this.heap[0];
    // 取出最后一个元素
    const last = this.heap.pop();

    if (!this.isEmpty()) {
      // 把最后一个元素放到根
      this.heap[0] = last;
      // “下沉”调整
      this.siftDown(0);
    }
    return top;
  }
  // 新元素插到末尾，可能比父节点小，破坏了“最小堆”性质
  // 所以要不断的跟父节点进行比较，如果更小，就交换，知道合适位置
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
  // 下沉
  private siftDown(i: number): void {
    const n = this.heap.length;
    // 非叶子节点范围 [0, half)
    const half = n >>> 1;

    while (i < half) {
      let child = (i << 1) + 1; // 左子节点
      const right = child + 1;
      // 选择更小的子节点
      // 如果右孩子存在，且，比左孩子更小，选右孩子
      if (right < n && this.compare(this.heap[right], this.heap[child]) < 0) {
        child = right;
      }

      // 如果当前节点 ≤ 最小孩子，停止
      if (this.compare(this.heap[i], this.heap[child]) <= 0) break;

      // 否则交换
      [this.heap[i], this.heap[child]] = [this.heap[child], this.heap[i]];

      i = child; // 继续向下查找
    }
  }
}

三、使用

数字最小堆
const heap = new MinHeap<number>();

heap.push(5);
heap.push(3);
heap.push(9);
heap.push(1);
heap.push(6);
// [1, 3, 9, 5, 6]
console.log(heap.heap);

四、使用场景

场景	说明
堆排序	原地排序，时间复杂度 `O(n ㏒ n )`
优先队列	任务调度、事件处理
Top-K 问题	找到最大的 K 个元素（用最小堆维护 K 个）
Dijkstra 算法	用堆优化最小距离节点
合并 K 个有序列表	每次取堆顶最小元素

五、注意事项

不要直接修改 heap 数组 ，否则会破坏堆结构
比较函数必须满足全序关系 ，即对任意 a ， b ， c ：可比、反对称、传递
性能：插入/删除均为 O(㏒ n) ，空间 O(n)

六、语言支持

语言	是否内置/优先列队	说明
C++	✅ 是	`std:priority_queue` 底层通常是二叉堆
Java	✅ 是	`java.util.PriorityQueue` 基于二叉堆
Python	✅ 是	`heapq` 模块，提供最小堆操作函数
C#	✅ `.NET 6+`	`PriorityQueue<T, TPriority>`
Go	❌ 否	需手动实现或用第三方库（如 `container/heap`
JavaScript	❌ 否	标注库没有堆，需要自己实现或用 npm 包
Rust	✅ 标准库	`std::collections::BinaryHeap` 最大堆

七、堆排序和快排

堆本身就是为了排序而生的。

时间复杂度 ： O(n ㏒ n)
空间复杂度 ： O(1) 原地排序
稳定性 ：不稳定
原理：
- 将数组 原地构建成最大堆 （ O(n) ）
- 重复执行：
  - 把堆顶（最大值）和末尾元素交换
  - 缩小堆范围，排除已排好的末尾
  - 堆新堆顶执行 siftDown
- 最终数组生序排列

	快速排序	堆排序	归并排序
平均时间	`O(n ㏒ n)`	`O(n ㏒ n)`	`O(n ㏒ n)`
最坏时间	`O(n²)`	`O(n ㏒ n)`	`O(n ㏒ n)`
空间	`O(n ㏒ n)`	`O(1)`	`O(n)`
实际速度	⚡️ 很快	🐢 很慢	快
稳定性	❌ 否	❌ 否	✅ 是

一、二叉堆​

二、实现（最小堆）​

三、使用​

四、使用场景​

五、注意事项​

六、语言支持​

七、堆排序和快排​