堆（二叉堆）
最后更新
二叉堆是一棵完全二叉树，它把最小值（最小堆）或最大值（最大堆）放在根节点。这里演示的是最小堆：每个父节点都小于或等于它的子节点。添加一个值时，先把它放到下一个空位，再让它“上浮”（sift up）：只要它比父节点小，就和父节点交换，直到重新满足堆的性质。点击上方的“播放”，观看每个新值如何一步步上浮到自己的位置。
因为堆是完全二叉树，所以可以紧凑地存放在数组里：节点 i 的子节点位于 2i+1 和 2i+2。插入和删除最小值都是 O(log n)（只走一条从根到叶的路径），查看最小值是 O(1)，这正是优先队列需要的。
时间复杂度与空间复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 查看最小值/最大值 | O(1) | 永远在根节点 |
| 插入（push） | O(log n) | 沿一条路径上浮 |
| 删除最小值/最大值 | O(log n) | 沿一条路径下沉 |
| 建堆 | O(n) | 一次性堆化 |
| 空间 | O(n) | 基于数组，不需要指针 |
分步说明（push）
| 步骤 | 发生了什么 |
|---|---|
| 1 | 把新值追加到末尾（下一个空的叶子位置）。 |
| 2 | 把它和父节点比较。 |
| 3 | 如果它更小（最小堆），就和父节点交换，向上移动。 |
| 4 | 重复以上步骤，直到它不再小于父节点，或者到达根节点。 |
实例演示
依次插入 [5, 3, 8, 1, 4]，建立一个最小堆：
| 插入 | 上浮后的数组 | 操作 |
|---|---|---|
5 | [5] | 第一个值成为根节点。 |
3 | [3, 5] | 3 小于父节点 5，交换后升到根节点。 |
8 | [3, 5, 8] | 8 大于父节点 5，留在叶子位置。 |
1 | [1, 3, 8, 5] | 1 小于父节点 5，交换；接着 1 小于父节点 3，再交换到根节点。 |
4 | [1, 3, 8, 5, 4] | 4 大于父节点 3，原地不动；最小值 1 仍在根节点。 |
什么时候用堆
| 适合使用 | 不适合使用 |
|---|---|
| 你需要反复从一个不断变化的集合中取出最小或最大的元素。 | 你需要查找任意值，而不仅仅是最值：这时用二叉搜索树或哈希集合。 |
| 你要为 Dijkstra、A* 或任务调度器实现优先队列。 | 你需要数据始终保持完全有序。 |
你想要 O(log n) 的插入和删除最小值，同时使用紧凑的数组布局。 | 你需要快速查找或删除某个特定的（非根）元素。 |
| 你需要合并一串数据流，并按优先级逐个取出。 | 数据量很小，线性扫描更简单，也足够快。 |
Heap (Priority Queue) 代码
简洁、可运行的 Heap (Priority Queue) 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Heap (Priority Queue) 的 Python 代码
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Heap (Priority Queue) 的 JavaScript 代码
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Heap (Priority Queue) 的 Java 代码
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Heap (Priority Queue) 的 C++ 代码
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Heap (Priority Queue) 的 C 代码
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}堆常见问题
堆有什么用？
堆用来实现优先队列，而优先队列支撑着 Dijkstra 最短路径算法、任务调度器和事件模拟。堆也是堆排序的核心。只要你需要反复从变化的集合中取出最小或最大的元素，堆就是合适的工具。
堆和二叉搜索树有什么区别？
两者都是二叉树，但二叉搜索树维持从左到右的完整顺序（因此能有序查找），而堆只保证父子之间的大小关系（最小值或最大值在根节点）。堆能以 O(1) 取得最值；二叉搜索树能以 O(log n) 查找任意值。
为什么堆要存放在数组里？
因为堆始终是一棵完全二叉树，它的节点可以完美对应到数组下标：下标
i 的子节点在 2i+1 和 2i+2，父节点在 (i-1)/2。这样不必存储子节点指针，缓存性能也非常好。堆和有序数组是一回事吗？
不是。堆只保证每个父节点比子节点小（最小堆）或大（最大堆），兄弟节点和堂兄弟节点之间没有特定顺序。有序数组完全有序，但插入要花
O(n)；堆插入只需 O(log n)，同时仍能立即取得最值。什么时候该用堆，而不是直接对数组排序？
当数据不断变化，而你只关心当前的最小值或最大值时，就用堆：每次插入和弹出都只需
O(log n)，不必重新排序整个数组。如果数据是静态的，而你需要所有元素都有序，一次 O(n log n) 的排序更简单，往往也更快。用 n 个元素建堆需要 O(n log n) 吗？
一次性建堆就不需要。逐个插入
n 个元素是 O(n log n)，但自底向上的 heapify 从最后一个父节点开始一路下沉到根节点，总共只需 O(n)，因为大多数节点都在底部，只需下沉很短的距离。相关资源
更多可视化
