堆 · 二叉堆 · 完全二叉树 · 大顶堆

🔷 概念关系总览（从大到小）

🧱 堆（Heap）
最抽象的概念

┃

🌳 二叉堆（Binary Heap）
最常用的堆实现

╰── 依赖 ──▶

📋 完全二叉树（Complete Binary Tree）
底层数据结构

┃

🔴 大顶堆（Max Heap）
父 ≥ 子

兄弟关系，互斥

🟢 小顶堆（Min Heap）
父 ≤ 子

完全二叉树是结构约束，大/小顶堆是顺序约束。
二叉堆 = 完全二叉树 + 大顶堆(或小顶堆)的顺序规则。

1. 完全二叉树（Complete Binary Tree）结构约束

定义：一棵二叉树，除最后一层外每一层都被完全填满，且最后一层的节点从左到右连续排列。

前 n-1 层是满二叉树（每层 2^k-1 个节点）
最后一层节点靠左填充，中间不能有空缺
可以用数组紧凑存储，不需要指针

✅ 完全二叉树

❌ 非完全二叉树（右子树缺左）

2. 二叉堆（Binary Heap）结构 + 顺序

定义：二叉堆 = 完全二叉树 + 堆序性（Heap Order Property）。

结构：用完全二叉树组织，保证可以用数组存储
堆序性：每个父节点的值 ≥ 所有后代（大顶堆）或 ≤ 所有后代（小顶堆）
注意：堆序性只约束父子关系，不约束兄弟大小

数组存储公式（下标从 0 开始）：
父节点下标：parent(i) = ⌊(i-1)/2⌋
左子节点：left(i) = 2i + 1　　右子节点：right(i) = 2i + 2

🔴 大顶堆（Max Heap）

父节点 ≥ 子节点，根节点是最大值

🟢 小顶堆（Min Heap）

父节点 ≤ 子节点，根节点是最小值

数组表示（以上面的大顶堆为例）：

50[0]

30[1]

20[2]

15[3]

10[4]

8[5]

7[6]

● 根节点（父） ● 内部节点（子） ● 叶子节点

3. 堆（Heap）— 最抽象的概念抽象数据类型

定义：堆是一个满足堆序性的树形数据结构，不限制分支数量。

堆是最抽象的概念，只要求"父节点和子节点满足某种大小关系"
可以是二叉堆（每个节点最多 2 个子节点）
也可以是多路堆（如 3-堆、4-堆、d-叉堆）
还可以是斐波那契堆、左偏堆、二项堆等更复杂的结构

💡 一句话总结关系

日常说的「堆」几乎总是指「二叉堆」，而「二叉堆」的底层就是一个「完全二叉树」用数组存的。大顶堆和小顶堆只是二叉堆的两种排序方向，互为「镜像」关系。

📊 五者核心区别对比

概念	性质	结构约束	顺序约束	常见用途
堆	抽象数据类型	无（树形即可）	父与子满足大小关系	优先队列
二叉堆	堆的具体实现	完全二叉树	父 ≥ 子或父 ≤ 子	堆排序、优先队列
完全二叉树	树的结构分类	层满 + 从左填充	无	二叉堆的底层结构
大顶堆	二叉堆的一种	完全二叉树	parent ≥ child	找最大值（如调度器）
小顶堆	二叉堆的一种	完全二叉树	parent ≤ child	找最小值（如Dijkstra）

⏱ 二叉堆关键操作复杂度

操作	时间复杂度	说明
取顶（查看根）	O(1)	数组第一个元素即为极值
插入	O(log n)	末尾追加 → 上浮（sift up）
删除堆顶	O(log n)	末尾换到根 → 下沉（sift down）
建堆	O(n)	从最后一个非叶节点逐个下沉
堆排序	O(n log n)	原地排序，不稳定

🎯 最后的澄清：常见误区

误区	真相
「堆是一个有序数组」	堆不是有序数组。只保证根是极值，左右子树没有全局有序性
「BST（二叉搜索树）和堆一样」	不同：BST 是中序有序，堆只保证父子大小关系
「堆的左子树一定 ≥ 右子树」	不一定。堆序性只约束父子，不约束兄弟
「完全二叉树就是满二叉树」	不同：满二叉树每层都满；完全二叉树最后一层可以不满但必须从左填充

堆 · 二叉堆 · 完全二叉树 · 大顶堆 · 小顶堆