为什么二叉堆一定是完全二叉树？
Zin*_*ing 8 heap data-structures
堆属性说：
如果 A 是 B 的父节点，则节点 A 的键相对于节点 B 的键进行排序，并在整个堆中应用相同的排序。要么父节点的键总是大于或等于子节点的键，最高键在根节点（这种堆称为最大堆）要么父节点的键小于或等于子节点和最低键位于根节点（最小堆）中。
但是为什么在这个wiki 中，二叉堆必须是一个完整的二叉树？在我的印象中，堆属性并不意味着这一点。
数组中的每个项目在二叉树中都有一个位置，并且该位置是根据数组索引计算的。定位公式确保树“紧密排列”。
例如，这里的二叉树：
由数组表示
[1, 2, 3, 17, 19, 36, 7, 25, 100].
请注意，数组的排序方式就像从树的顶部开始，然后从左到右读取每一行一样。
如果您向此数组添加另一个项目，它将代表19 下面和 100 右侧的槽。如果这个新数字小于 19，则必须交换值，但尽管如此，这就是槽将由数组的第 10 项填充。
另一种看待它的方法是：尝试构建一个不是完整二叉树的二叉堆。你确实不能。
如果树是完整的，则只能保证 O(log(n)) 插入和（根）删除。原因如下：
如果树不完整，那么它可能是不平衡的，在最坏的情况下，它只是一个链表，需要 O(n) 找到叶子，需要 O(n) 进行插入和删除。根据完整性的形状要求，您可以保证 O(log(n)) 操作，因为找到叶子（数组中的最后一个）需要恒定的时间，并且可以保证树的深度不超过 log2(N)，这意味着“冒泡”（用于插入）和“下沉”（用于删除）最多需要对堆中的数据进行 log2(N) 次修改（交换）。
话虽如此，您绝对不必拥有完整的二叉树，但您只是失去了这些运行时保证。此外，正如其他人提到的，拥有完整的二叉树可以轻松地以数组格式存储树，从而放弃对象引用表示。
小智 1
“完整”的意思是，在堆中，所有内部（非叶）节点都有两个子节点，除非没有子节点 - 所有内部节点都是“完整”的。当您添加到堆时，在开始新级别之前，从左侧开始填充最低级别的节点（使用无子叶节点）。当您从堆中删除节点时，最低级别的最右边的叶子也会被删除（并推回到顶部）。堆也完全平衡（万岁！）。
二叉堆可以看作是一棵二叉树，但节点没有子指针，并且插入（推入）和删除（弹出或从堆内部）与实际二叉树的过程有很大不同。
这是堆组织方式的直接结果。堆作为向量保存，节点之间没有间隙。堆中第 i 个项目的父项是 item (i - 1) / 2（假设是二元堆，并假设堆顶部是 item 0）。第 i 项的左子项是(i * 2) + 1，右子项比它大 1。n当堆中有节点时，如果(i * 2) + 1超过，则该节点没有左子节点n，如果超过，则没有右子节点(i * 2) + 2。
堆是一个美丽的东西。它的一个缺陷是您确实需要一个足够大的向量来容纳所有条目...与真正的二叉树不同，您不能一次分配一个节点。因此，如果您有一个用于无限数量项目的堆，则必须准备好在需要时扩展底层向量，或者运行一些可以像向量一样进行寻址的碎片结构。
FWIW：当走下堆时，我发现很方便走到右边的孩子——(i + 1) * 2如果是的< n话，那么两个孩子都存在，如果只有== n左边的孩子存在，否则没有孩子。