Heap

什么是堆

堆 (Heap) 是一种特殊的完全二叉树，它满足堆序性质：每个节点的值都不大于（或不小于）其父节点的值。

堆的核心价值：O(1) 时间拿到最值，O(log n) 时间插入和删除。

A heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is the parent node of C, then the key of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.

— Wikipedia: Heap

两个关键性质

堆由两个性质共同定义：

性质一：完全二叉树 (Shape Property)

所有层级都被填满，最后一层从左到右依次填充，中间不能有空缺。这保证了：

• 树的高度始终为 O(log n)，操作效率有保障
• 可以用数组紧凑存储，不需要指针，内存利用率高

flowchart TB
  subgraph good ["完全二叉树"]
    A((1)) --> B((3))
    A --> C((5))
    B --> D((7))
    B --> E((8))
    C --> F((9))
  end

性质二：堆序性质 (Heap Property)

• 最小堆 (Min-Heap)：父节点 <= 子节点，根节点是最小值
• 最大堆 (Max-Heap)：父节点 >= 子节点，根节点是最大值

重要区别：堆不是完全排序的数据结构。它只保证父子关系，兄弟节点之间没有大小保证。这就是堆和排序数组的根本区别。

数组存储

堆最巧妙的地方是用一维数组来存储一棵树，不需要任何指针。父子关系通过下标计算得到：

对于下标为 i 的节点（从 0 开始）：

示例（最小堆）：

树形表示:              数组表示:
        1               [1, 3, 5, 7, 8, 9, 6]
       / \               0  1  2  3  4  5  6
      3   5
     / \ / \
    7  8 9  6

为什么这样可行？因为完全二叉树没有空洞，数组的每个位置都会被填满，不会浪费空间。

核心操作

时间复杂度总览

push — 插入元素（上浮）

1. 将新元素追加到数组末尾
2. 与父节点比较，如果违反堆序性质就交换
3. 重复向上比较，直到满足堆序或到达根节点

flowchart TB
  subgraph step1 ["Step 1: 插入 2 到末尾"]
    A1((1)) --> B1((3))
    A1 --> C1((5))
    B1 --> D1((7))
    B1 --> E1((8))
    C1 --> F1((9))
    C1 --> G1((2))
    style G1 fill:#fbbf24,color:#000
  end
  subgraph step2 ["Step 2: 2 比 5 小, 交换"]
    A2((1)) --> B2((3))
    A2 --> C2((2))
    B2 --> D2((7))
    B2 --> E2((8))
    C2 --> F2((9))
    C2 --> G2((5))
    style C2 fill:#fbbf24,color:#000
  end
  subgraph step3 ["Step 3: 2 比 1 大, 停止"]
    A3((1)) --> B3((3))
    A3 --> C3((2))
    B3 --> D3((7))
    B3 --> E3((8))
    C3 --> F3((9))
    C3 --> G3((5))
    style C3 fill:#34d399,color:#000
  end
  step1 --> step2 --> step3

pop — 删除最值（下沉）

1. 保存根节点（最值）作为返回值
2. 将数组最后一个元素移到根节点位置
3. 与子节点比较，与更小的子节点（最小堆）或更大的子节点（最大堆）交换
4. 重复向下比较，直到满足堆序或到达叶节点

为什么用最后一个元素替换根节点？因为删除数组末尾元素是 O(1)，而删除开头会导致整个数组移位 O(n)。

heapify — 建堆 O(n)

从一个无序数组构建堆，Floyd 算法的做法：

1. 从最后一个非叶节点（下标 Math.floor(n/2) - 1）开始
2. 对每个节点执行下沉操作
3. 一直处理到根节点

为什么是 O(n) 而不是 O(n log n)？因为大部分节点在树的底部，下沉距离很短。叶节点（占一半）不需要操作，倒数第二层只下沉 1 层，只有根节点需要下沉 log n 层。数学上这个级数收敛到 O(n)。

参考：GeeksforGeeks: Time Complexity of Building a Heap

交互演示

下面是一个可视化的最小堆，你可以插入和删除元素，观察上浮和下沉的过程：

JavaScript 实现

JavaScript 没有内置的堆/优先队列（不像 Python 的 heapq 或 Java 的 PriorityQueue）。下面是一个完整的 MinHeap 实现（点击左下角 Console 查看输出）：

实现要点：

• 数组存储：用普通数组 this.heap = [] 存储，无需指针
• 上浮 (Sift Up)：插入时新元素从末尾向上比较，比父节点小就交换
• 下沉 (Sift Down)：删除时根节点向下比较，与更小的子节点交换
• 建堆 (fromArray)：从最后一个非叶节点 Math.floor(n/2) - 1 开始逐个下沉，时间复杂度 O(n)
• 最大堆：只需将所有 < 比较改为 > 即可

应用场景

优先队列 (Priority Queue)

堆是优先队列最常见的底层实现。优先队列的特点是出队顺序由优先级决定，而不是先进先出。

典型场景：任务调度、事件驱动模拟、操作系统进程管理。

堆排序 (Heap Sort)

利用堆进行排序，时间 O(n log n)，空间 O(1)（原地排序）：

1. 建最大堆 — O(n)
2. 依次将根节点（最大值）与末尾交换，缩小堆的范围，执行下沉 — O(n log n)

参考：GeeksforGeeks: Heap Sort

Top-K 问题

找出 n 个元素中最大的 K 个：

• 维护一个大小为 K 的最小堆
• 遍历元素，比堆顶大就替换堆顶并下沉
• 最终堆中就是最大的 K 个元素
• 时间 O(n log K)，远优于完整排序 O(n log n)

中位数维护 (Two-Heap)

用两个堆实时维护中位数：

• 最大堆：存较小的一半
• 最小堆：存较大的一半
• 保持两个堆大小差不超过 1
• 中位数从堆顶 O(1) 获取

flowchart LR
  subgraph maxHeap ["Max-Heap (smaller half)"]
    direction TB
    A((3)) --> B((2))
    A --> C((1))
  end
  subgraph minHeap ["Min-Heap (larger half)"]
    direction TB
    D((5)) --> E((7))
    D --> F((9))
  end
  maxHeap -->|"median = (3+5)/2 = 4"| minHeap

图算法

• Dijkstra 最短路径：用最小堆（优先队列）每次取出距离最小的未访问节点 — O((V + E) log V)
• Prim 最小生成树：用最小堆选取权重最小的边

堆 vs 其他数据结构

选择建议：

• 只需要快速取最值 + 插入 -> 堆
• 需要快速搜索 + 有序遍历 -> 平衡 BST
• 数据基本不变，需要二分查找 -> 排序数组

参考：Baeldung: Heap vs Binary Search Tree

LeetCode 常见题型

JavaScript 刷题时可以使用 LeetCode 内置的 @datastructures-js/priority-queue 包，无需手写堆。

参考资料

• Wikipedia: Heap
• Wikipedia: Binary Heap
• GeeksforGeeks: Binary Heap
• GeeksforGeeks: Heap Sort
• Programiz: Heap Data Structure
• Stanford CS 161: Lecture 4
• Carnegie Mellon: Binary Heaps
• Tech Interview Handbook: Heap