二叉堆

概述

二叉堆（Binary Heap） 是一种用数组表示的近似完全二叉树（complete binary tree），满足堆性质（heap property）：最大堆中每个节点的值不小于其子节点的值，最小堆中每个节点的值不大于其子节点的值。

定义

二叉堆

二叉堆是一个数组对象 $A$，可被视为一棵近似完全二叉树。树中每个节点与数组中存放该节点值的下标相对应。

对于下标 $i$（从 1 开始），其：

• 父节点：$\text{PARENT}(i)=\lfloor i/2\rfloor$
• 左子节点：$\text{LEFT}(i)=2i$
• 右子节点：$\text{RIGHT}(i)=2i+1$

最大堆性质：对每个节点 $i$（除根外），有 $A[\text{PARENT}(i)]\ge A[i]$。

最小堆性质：对每个节点 $i$（除根外），有 $A[\text{PARENT}(i)]\le A[i]$。

核心性质

数组表示与索引操作

• $\text{PARENT}(i)$、$\text{LEFT}(i)$、$\text{RIGHT}(i)$ 均可在 $O(1)$ 时间内完成计算。
• 无需使用指针或额外存储，数组本身即隐含了树的结构。

高度与规模

• 含 $n$ 个元素的堆的高度为 $\lfloor \lg n\rfloor$。
• 叶节点的下标范围为 $\lfloor n/2\rfloor +1$ 到 $n$。
• 非叶节点的下标范围为 $1$ 到 $\lfloor n/2\rfloor$。

堆排序中的应用

• 最大堆的根节点 $A[1]$ 始终是堆中的最大元素。
• 最小堆的根节点 $A[1]$ 始终是堆中的最小元素。
• 二叉堆是 堆排序 和 优先队列 的基础数据结构。

章节扩展

第6章：堆排序

二叉堆是堆排序算法的核心数据结构。通过 BUILD-MAX-HEAP 将输入数组构建为最大堆，然后反复取出堆顶最大元素完成排序。

第6章：优先队列

二叉堆也是实现 优先队列 的高效结构，支持插入、取最大值、删除最大值等操作。

参见

• 数据结构
• 优先队列
• MAX-HEAPIFY
• BUILD-MAX-HEAP