logo标签列表

为什么二叉堆必须是完全二叉树？

data-structuresbinary-treeheap
11
堆属性定义如下:
如果 A 是 B 的父节点，则节点 A 的键按照堆中的相同顺序与节点 B 的键排序。父节点的键始终大于或等于子节点的键，且最高键位于根节点(此类堆称为最大堆)，或者父节点的键小于或等于子节点的键，且最低键位于根节点(此类堆称为最小堆)。
但是为什么在这个维基百科中，二叉堆必须是一个完全二叉树？在我印象中，堆属性并不意味着这一点。
1
这棵树是一棵完全二叉树；也就是说，除了最后一层（最深的一层）可能不满外，其它所有层都是满的，并且如果最后一层不满，那么该层的节点将从左到右填充。这样做只是为了保持任意节点高度接近其理想值，以实现良好的运行时性能。 - phs
8个回答
9
根据你提供的wikipedia article，二叉堆必须符合堆属性（如你所讨论的）和形状属性（它要求它是一个完全二叉树）。没有形状属性，数据结构提供的运行时优势将会丧失（即完整性确保在删除元素时有明确定义的方法来确定新的根节点等）。
5
只有在树是完全的情况下，才能保证O(log(n))的插入和(根)删除。原因如下：
如果树不完整，则可能不平衡，在最坏的情况下，仅为一个链接列表，需要O(n)找到叶子节点，并且需要O(n)进行插入和删除。通过完整性的形状要求，您可以保证O(log(n))操作，因为查找叶子（数组中的最后一个）需要恒定时间，并且可以保证树的深度不超过log2(N)，这意味着“冒泡”（用于插入）和“下沉”（用于删除）将需要最多log2(N)次数据交换。
话虽如此，您并不一定需要完整的二叉树，但您会失去这些运行时保证。此外，正如其他人所提到的，拥有完整的二叉树使得将树存储在数组格式中变得容易，从而放弃了对象引用表示。
5
在数组中，每个项目都在二叉树中占据一个位置，该位置是由数组索引计算出来的。定位公式确保树是“紧密包装”的。
例如，这棵二叉树： enter image description here 用数组表示为：
[1, 2, 3, 17, 19, 36, 7, 25, 100].

请注意，这个数组的顺序就像你从树的顶部开始，从左到右读取每一行的顺序一样。
如果您向此数组添加另一个项目，则它将代表19下方和100右侧的插槽。如果此新数字小于19，则值必须进行交换，但无论如何，该数组的第10个项目都将填充该插槽。
另一种看待它的方法是：尝试构建不完整二叉堆。您实际上是做不到的。
1
'complete' 的意思是，在堆中所有内部（非叶子）节点都有两个子节点，除非没有子节点了——所有内部节点都是 'complete'。当你向堆中添加元素时，最低层的节点会从左边开始填充（用无子节点的叶节点），然后才会开始新的一层。当你从堆中删除节点时，最底层最右边的叶节点会被删除（并在顶部重新插入）。堆也是完美平衡的（万岁！）。
二叉堆可以看作是二叉树，但是节点没有子指针，并且插入（push）和删除（pop或从堆内部删除）与实际二叉树的过程有很大不同。
这是堆的组织方式直接导致的结果。堆被保存为一个向量，节点之间没有空隙。假设使用二叉堆，并且堆顶是第0项，则第i项的父项是项目(i-1)/2。第i项的左子项是(i*2)+1，右子项比它大1。当堆中有n个节点时，如果(i*2)+1超过了n，则该节点没有左子项；如果(i*2)+2超过了n，则该节点没有右子项。
堆是一件美妙的事情。它唯一的缺点是您需要一个足够大的向量来容纳所有条目...与真正的二叉树不同，您不能一次分配一个节点。因此，如果您有一个用于无限数量项的堆，则必须准备在需要时扩展底层向量，或者运行一些可以像向量一样寻址的分散结构。

FWIW：在向下遍历堆时，我发现将步骤移到右子节点很方便——(i + 1) * 2——如果它是< n，则两个子节点都存在，如果它是== n，则只有左子节点存在，否则没有子节点。

1
通过将二叉堆维护为完全二叉树，可以获得多个优点，例如： 1. 堆是完全二叉树，因此堆的高度是最小可能的，即log（树的大小）。插入、构建堆操作取决于高度。因此，如果高度最小，则它们的时间复杂度将减少。 2. 完全二叉树的所有项以连续的方式存储在数组中，因此可以进行随机访问，并且还提供缓存友好性。
0
堆的底层结构是一个数组，其中每个节点都是数组中的索引。因此，如果树不完整，这意味着其中一个索引被保留为空，这是不可能的，因为它是以每个节点作为索引的方式编码的。我在下面提供了一个链接，以便您可以看到堆结构是如何构建的。

http://www.sanfoundry.com/java-program-implement-min-heap/

希望能有所帮助

0

为了使二叉树成为堆，它必须满足两个条件。1）它必须具有堆属性。2）它必须是完全二叉树。

一个结构可能具有其中一个属性而不具备另一个属性，但我们不会称这样的数据结构为堆。您说得对，堆属性并不包含形状属性。它们是独立的约束条件。

0

我发现到目前为止所有的答案要么没有回答问题，要么本质上说“因为定义是这样说的”，或者使用类似循环论证的方式。它们肯定是正确的，但对我来说不是很有信息量。

我立即意识到堆必须是一棵完全二叉树，因为我记得在堆中插入新元素时不是放在根节点（就像在二叉搜索树中那样），而是放在右下角。

因此，在堆中，新元素从下往上传播 - 它在树内“向上移动”直到找到一个合适的位置。

在二叉搜索树中，新插入的元素朝相反的方向移动 - 它被插入到根部并且“向下移动”，直到找到它的位置。

堆中每个新元素都从底部右侧节点开始，这意味着堆始终是一棵完全二叉树。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接