关于二进制堆数据结构的问题

Question

我一直在不同的网站和书籍上阅读，我有一些问题需要解决。

1:父节点的优先级是否总是高于其任一子节点的优先级？

2：左兄弟的优先级总是低于右兄弟的优先级吗？

3：每个级别都满了吗？可能除了最上面的级别，它是正确加载的吗？

4:每个级别都满了吗？除了最底层可能是满的。

Answer 1

来源https://en.wikipedia.org/wiki/Binary_heap:

二进制堆被定义为具有两个附加约束的二进制树：[3]

• Shape属性：二进制堆是一个完整的二进制树；也就是说，树的所有级别(可能除了最后一个(最深的((都被完全填充，如果树的最后一个级别不完整，则该级别的节点将从左到右填充
• 堆属性：根据某个总顺序，每个节点中存储的密钥要么大于或等于(≥(，要么小于或等于(≤(节点子节点中的密钥

关于您的问题：

1：父节点的优先级是否总是高于其任何子节点的优先级？

在最大堆中，父节点的优先级总是大于或等于其子节点的优先级。

2：左同级的优先级总是低于右同级的优先级吗？

绝对不是！以下两个都是有效的最大堆：

3           3
/          / 
2   1       1   2

在维护Shape属性的同时，试图维护左子项和右子项的顺序是愚蠢的。这是可以做到的，但要付出巨大的效率代价。

关于问题3和4，请参阅上面对Shape属性的讨论。特别是。

3：每个级别都满了吗，除了可能是右加载的顶层？

否。

4：每个级别都满了吗，可能除了底部级别，它是左加载的。

是。Shape属性就是这么说的。

Answer 2

在了解堆之前，您应该了解完全二叉树(CBT(和几乎完全二叉树法(ACBT(的定义。

CBT和ACBT

完整二叉树：完整的二叉树是指除叶子以外的每个节点都有两个子节点的树。

几乎完全二叉树：在每个节点的给定二叉树中：

1. 填充左子项后，只填充右子项
2. 填充当前级别后，只填充下一级别

现在，让我们来看看二进制堆的定义：

二进制堆是一个完整的二进制树或几乎完全的二进制树(所有级别都已完全填充，除了最后一级可能有所有键尽可能剩余，即左加载(。此属性适用于将堆存储在数组中。

二进制堆的类型：

最大堆：在给定的ACBT或CBT中；父根与子根相比最大或相等。

最小堆：在给定的ACBT或CBT中；父节点在比较其子节点时最小或相等。

这个解释将澄清你所有的问题，但让我为你总结一下。

1. 这里不考虑优先级。在这里，无论您遵循什么顺序(基于Max或Min堆(，都必须为每个节点遵循。您需要记住的唯一一点是，在最大堆父节点为最大或等于其子节点的情况下，在最小堆中反之亦然。你不在乎左孩子或右孩子。这在二进制搜索树(BST(中得到了注意

2. 所有级别都是满的，除了最后一个级别可能有尽可能多的键(我指的是孩子(。

3. 在二进制堆中，如果堆是一个具有N个节点的完整二进制树，则它具有最小的可能高度，即log₂N。

有一个惊人的链接，您可以参考它来更好地了解堆。