这是堆栈和队列文章结尾预告的数据结构系列第 2 篇。本篇主角是堆，但开始前要先澄清一个误解。
相关文章堆栈与队列完整总结：Swift 没有 Stack 类型的原因（包括 removeFirst 陷阱）中可以同时了解背景概念和后续应用案例。
**数据结构中的堆只与内存堆同名，完全没有关系。**内存的堆区域是动态分配空间，而本文讨论的堆是“用于以 O(1) 取出最小值（或最大值）的树”。
内存分配区域的区别会在堆栈 vs 堆中单独说明。本文只关注数据结构 Heap 和 Priority Queue。
如果你期待的是“堆栈 vs 堆”文章里的那个堆，这里是完全不同的世界。
堆要解决的问题很明确。
“我想先处理最紧急的事情，但为了此事把全部内容排好序太浪费了。”
排序是过度处理
假设要创建一个优先取出最高优先级任务的队列。每次对数组排序，插入一次就要 O(n log n)。
即使保持有序并寻找插入位置，移动元素也需要 O(n)。
仔细想想，我们需要的并不是整体有序。只要能立即知道当前最紧急的一项就够了。
等第一名被取出后再确认第二名是谁，也完全不迟。
堆恰好只做这一项保证。因此插入和删除都能在 O(log n) 内完成。
“承诺越少，速度越快”是数据结构设计中典型的权衡。
堆的规则：父节点小于子节点，仅此而已
最小堆是完全二叉树，并且只有一条规则。
所有父节点都小于或等于自己的子节点。
兄弟节点谁更大并不重要。左子树也不必小于右子树。
只要遵守父子关系即可。这种宽松性保证根节点始终是全局最小值，但除此之外不做保证。
插入（sift up）：添加到树的末尾后，如果小于父节点，就与父节点交换并向上移动。只移动树高，因此是 O(log n)。
取出最小值（sift down）：移除根节点，把末尾元素移到根，再与两个子节点中较小的那个交换并向下移动。同样是 O(log n)。
用数组构建树的魔法
堆的实现优雅之处就在这里。完全二叉树从左到右连续填充，因此可以不使用指针按顺序放入数组。（NIST Heap）。
索引: 0 1 2 3 4 5
值: [1, 3, 2, 7, 4, 5]只要计算索引，就能得到父子关系。
- 父节点：
(i - 1) / 2 - 左子节点：
2i + 1，右子节点：2i + 2
没有节点对象、子节点指针，也没有堆内存分配。既享受数组 vs 链表中提到的缓存局部性优势，又只借用树的逻辑结构。
用 Swift 写出的骨架如下。
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDown就是上面介绍的重复交换。
顺带一提，把现有数组整体构建成堆的 build-heap 并不是逐个插入的 O(n log n)。从下半部分开始 sift down，可以在**O(n)**内完成——这是面试中经常出现的细节。
堆在实际开发中的定位
**优先队列就是堆。**借用堆栈和队列文章的说法，队列按到达顺序取出，优先队列按紧急程度取出，而堆是它的标准实现（NIST Priority Queue）。
- OS 调度器：优先给高优先级进程分配 CPU
- Dijkstra 最短路径：反复取出“目前发现的路径中最短的一条”的算法；没有堆，性能会崩溃
- 定时器管理：系统内部只需知道大量定时器中最先响起的那个
- 堆排序：全部放入再全部取出，就能完成 O(n log n) 排序。优点是无需额外内存即可原地排序
- Top-K 问题：“维护数据流中最大的 K 个”——用大小为 K 的最小堆可在 O(n log K) 内解决，是编程测试中的经典模式
Swift 标准库没有堆。和堆栈、队列文章中的 Deque 一样，Apple 的swift-collections包提供了Heap（swift-collections Heap）。
这是一个同时以 O(log n) 支持 min 和 max 的 min-max heap 实现。如果像编程测试那样不能使用外部包，熟练掌握上面的 MinHeap 骨架更实用。
总结
- 数据结构中的堆与内存堆只是名称相同——它是“立即取出最小值的树”
- 规则只有父节点 ≤ 子节点——放弃整体排序，换来插入和删除 O(log n)
- 因为是完全二叉树，所以可以不使用指针放在数组中——父节点
(i-1)/2、子节点2i+1、2i+2 - 优先队列的标准实现是堆，代表性用途包括 Dijkstra、调度器和 Top-K
- Swift 使用 swift-collections 的
Heap，编程测试中则以自行实现为标准
下一篇是哈希表。我们将讨论 Swift Dictionary 如何实现 O(1)，以及 Hashable 要求的真正含义。
来源与验证
- swift-collections HeapApple · 官方文档 · 核查 2026年8月17日依据: Swift Heap API 与最小堆、最大堆的行为
- NIST Dictionary of Algorithms: Priority QueueNIST · 官方数据 · 核查 2026年8月17日依据: 优先队列抽象数据类型的定义
- NIST Dictionary of Algorithms: HeapNIST · 官方数据 · 核查 2026年8月17日依据: 基于数组的堆结构与操作特性