为什么堆必须是几乎完全二叉树？能否基于完全或满二叉树实现？

先纠正下你对两种树结构的理解误区：

• 几乎完全二叉树（也就是标准定义里的完全二叉树）：除了最后一层，其他所有层的节点都被填满；最后一层的节点必须从左到右连续排列，不能有间隔。
• 满二叉树：每一层的节点都被完全填满，没有任何空缺，节点总数一定是 2^h - 1（h是树的高度）。

接下来解释核心原因：

1. 空间不浪费，利用率拉满 #

满二叉树要求每一层都必须填满，只要你的节点数不是刚好凑成 2^h - 1，就得额外填一堆空节点来凑结构，纯纯浪费空间。比如存5个节点，满二叉树得要7个节点的位置（高度3），其中2个是空的，完全没必要。

而几乎完全二叉树允许最后一层不满，只要节点靠左排，就能用最少的空间装下所有节点，空间利用率接近100%，没有冗余。

2. 数组存储的爽快感 #

二叉堆一般用数组实现，靠几乎完全二叉树的特性，能用简单的数学公式直接定位任意节点的父节点、左右孩子：

• 父节点索引：parent(i) = floor((i-1)/2)
• 左孩子索引：left(i) = 2*i + 1
• 右孩子索引：right(i) = 2*i + 2

要是用满二叉树，节点数不够时数组里会有大量空位置，不仅浪费空间，还会打乱这种索引计算的连续性，搞个操作都得额外判断空节点，麻烦得很。

3. 堆操作效率有保证 #

堆的插入、删顶这些核心操作要维护堆的性质，得做节点上浮、下沉。几乎完全二叉树的高度是 O(log n)，这保证了这些操作的时间复杂度是 O(log n)。

换成满二叉树的话，节点数不够时树的高度会更高（因为要填空节点凑高度），上浮下沉的步骤变多，效率直接下降。而且空节点的存在还得加一堆判断逻辑，操作复杂度飙升。

4. 适配实际场景的灵活性 #

实际用堆的时候，数据量哪能刚好凑成 2^h - 1 啊？满二叉树的死限制根本没法灵活应对任意数量的元素。而几乎完全二叉树不管你存1个还是1000个节点，都能保持紧凑的结构，完美适配各种场景。

说白了，几乎完全二叉树在空间利用率、存储效率、操作复杂度和场景适配性上都甩满二叉树几条街，这就是二叉堆选它当基础结构的原因。

内容的提问来源于stack exchange，提问作者Dhruv Chopra