什么是堆？大顶堆和小顶堆有什么区别？堆和优先队列是什么关系？

简化版

堆是一棵完全二叉树，且满足「堆序」：大顶堆每个节点都 ≥ 它的孩子（堆顶是最大值）；小顶堆每个节点都 ≤ 它的孩子（堆顶是最小值）。堆只保证「父子」之间的大小关系，不保证兄弟或整体有序。优先队列是一种「每次取出优先级最高元素」的抽象数据结构，它最常用堆来实现——所以两者经常被当成一回事。

详细版

堆的两个条件：

结构性：是一棵完全二叉树（除最后一层外都填满，最后一层从左往右连续排列）。
堆序性：
- 大顶堆（Max-Heap）：任意节点的值 ≥ 其孩子 → 根是最大值。
- 小顶堆（Min-Heap）：任意节点的值 ≤ 其孩子 → 根是最小值。

大顶堆:            小顶堆:
      9                1
     / \              / \
    7   8            3   2
   / \              / \
  3   5            7   6

关键：堆是偏序不是全序——只约束父子，不保证左右孩子谁大、也不保证跨子树的顺序。所以堆不是「排好序的」，只是「堆顶是极值」。

堆 vs 优先队列：优先队列是「逻辑概念」（支持插入、取出最值），堆是「实现手段」。绝大多数优先队列底层就是二叉堆。

完整版教学

一、堆的两个核心特征

理解堆要抓住两点：它是完全二叉树（结构规整，所以能用数组紧凑存储），它满足堆序（父子间有固定大小关系，所以堆顶恒为极值）。这两点缺一不可：只满足堆序不是完全二叉树，就没法用数组高效存；只是完全二叉树不满足堆序，堆顶就不是极值了。

二、大顶堆 vs 小顶堆

两者结构完全一样，只是堆序方向相反：

大顶堆：父 ≥ 子，堆顶（根）是整个堆的最大值。适合「反复取最大值」。
小顶堆：父 ≤ 子，堆顶是最小值。适合「反复取最小值」。

用哪种取决于你要频繁取最大还是最小。很多题的技巧就藏在「该用大顶堆还是小顶堆」的选择里（比如求最大 K 个反而用小顶堆，见 Top K 专题）。

三、为什么强调「偏序、不是全序」

这是最容易误解的点。堆只保证父 ≥（或 ≤）子，但：

不保证左孩子和右孩子谁大谁小。
不保证不同子树之间的顺序（比如左子树的某个节点可能比右子树的根还大）。

所以堆不是排好序的数组，你不能像 BST 那样中序遍历得到有序序列。堆能高效做的只有一件事：O(1) 看到极值、O(log n) 取出极值。想要「有序」得靠堆排序（反复取极值）。

四、堆能做什么、不能做什么

擅长：反复获取/删除最大或最小值（O(log n)）、查看极值（O(1)）、动态维护一批数据的 Top K。
不擅长：查找任意元素（O(n)，因为无序）、范围查询、按序遍历。

所以「需要频繁拿极值」就用堆，「需要有序/范围查询」用平衡 BST，「按 key 快速存取」用哈希表。

五、堆和优先队列的关系

优先队列（Priority Queue） 是一个抽象数据类型：元素带优先级，出队时总是弹出优先级最高的（而不是像普通队列 FIFO）。它可以用多种方式实现（有序数组、链表、堆…），但二叉堆是最常用、综合最优的实现：插入和取极值都是 O(log n)。所以工程里「优先队列」和「堆」几乎画等号——Java 的 PriorityQueue、C++ 的 priority_queue 底层都是堆。

六、常见误区与追问

考点	正确口径
结构性质	完全二叉树
堆序性质	父节点不小于或不大于孩子
能力边界	只能快速拿最大/最小，不能保持全序

maxHeap:
for every edge parent -> child:
  parent.value >= child.value
peek root = maximum

堆是偏序结构：堆顶最优，但除了父子关系外，别的位置没有排序承诺。

误区：堆中从左到右就是有序数组。 堆只保证父子顺序，层内和左右子树之间不保证大小关系。
误区：大顶堆的左孩子一定大于右孩子。 堆没有兄弟之间的顺序要求，只要求父节点和孩子满足堆序。
误区：优先队列就是一种堆。 优先队列是抽象数据类型，堆是它最常见的底层实现。
追问：堆为什么必须是完全二叉树？ 完全二叉树能用数组紧凑存储，并保证插入删除只影响末尾和一条路径。
追问：大顶堆和小顶堆怎么选？ 需要反复取最大用大顶堆，需要反复取最小用小顶堆；Top K 常反着选。
追问：堆的基本操作复杂度是多少？ peek O(1)，insert 和 poll 通过上浮/下沉调整，都是 O(log n)。

七、加强记忆

堆 = 完全二叉树 + 堆序：大顶堆父 ≥ 子、堆顶最大；小顶堆父 ≤ 子、堆顶最小。堆是偏序（只管父子，不保证兄弟/跨子树顺序），所以不是有序的，只擅长 O(1) 看极值、O(log n) 取极值。优先队列是「每次取优先级最高」的抽象类型，最常用堆实现，两者常被视为一回事。

简化版

详细版