为什么堆几乎是完全二叉树？

Question

我在很多书中读到，二叉堆几乎是完整的二叉树。据我所知，几乎完全二叉树的最后第二层未填充ALWAYS并且从左到右。并且，完整二叉树可能或可能不总是填充最后一个元素，但最后第二层必须始终填充，就像几乎完整的二叉树一样。

在这方面，我还阅读了二叉堆**必须**几乎完整的二叉树。我不得不问为什么？堆不能在完整二叉树或完全树上实现吗？

在学习二叉堆和堆排序时，我总是看到几乎完全二叉树。我想知道为什么？为什么不在完全填充的二叉树中？

Answer 1

这种混乱来自于“几乎完全二叉树”的语法含义和同一概念的技术含义之间的差异。

从语法上讲，

<almost complete X>

表示某事物接近完全X，但不完全是X。然而，在技术细节上，

<almost complete X>

通常意味着该事物与X的距离不远于“几乎完成”。

从技术上讲，几乎完全二叉树是这样的二叉树：如果忽略最后一层 n，那么它上面的子树就是完全二叉树，每个层（除了最后一层）都具有所有可能的节点。

但是，在最后一层，几乎完整的二叉树可能是完整的，也可能不是完整的。节点从上到下、从左到右插入到几乎完整的二叉树中，新节点位于顶部的优先级高于左侧。

完全二叉树有

sum(2^0 + 2^1 + ... + 2^n) = 2^(n+1) - 1 个节点，高度为 log(2, n)。

因此，完全二叉树是几乎完全二叉树的一种特定可能状态。

所以，在这种情况下，“几乎”并不意味着“不完全但接近”。它的意思是“离接近不远了”，作为一个特定的可能情况，它具有完整性。