data-structures - 为什么这个二叉树不是堆？

Question

我一直在自学考试，遇到了以下问题:

“给出以下二叉树不是堆的两个不同原因”

    91
   /  \
  77  46
 /  \   \
68  81   11

我知道其中一个原因是因为堆的子堆必须小于或等于其父堆的值，所以 81 违反了此规则 81 > 77，但我不确定其他答案。

有人可以澄清一下吗？

Answer 1

11 应该是 46 的左 child ，而不是右 child 。

Wikipedia提到二进制堆应该是 complete binary tree ，这意味着“每一层，可能除了最后一层，都被完全填充，并且所有节点都尽可能地向左”，如果 11 显然不是这种情况现在在哪里。

这样做的好处很容易理解 - 给定堆的大小，您可以快速确定底层最后一个节点的位置，这是插入和删除所必需的。如果我们使用数组表示，它就像 heap size - 1 处的元素是最后一个元素一样简单。对于基于指针的表示，我们可以很容易地确定我们应该向左还是向右移动以到达最后一个元素。

如果堆不是完整的二叉树，可能还有其他方法可以获得相同的性能，但它们可能会增加复杂性。