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

Question

我一直在教自己考试,并遇到了以下问题:

"给出以下二元树不是堆的两个不同原因"

    91
   /  \
  77  46
 /  \   \
68  81   11

我知道其中一个原因是因为堆的子项必须小于或等于其父项的值,因此81违反此规则81 > 77,但我不确定另一个答案.

有人可以澄清一下吗？

Answer 1

11应该是左孩子46,而不是右孩子.

维基百科提到二进制堆应该是一个完整的二叉树,这意味着"每个级别,除了可能是最后一个,完全填充,并且所有节点都尽可能地离开 ",显然不是这样的情况,如果11它在哪里现在.

这有利的原因相当容易理解 - 考虑到堆的大小,您可以快速确定底层最后一个节点的位置,这对于插入和删除是必要的.如果我们使用数组表示,它就像heap size - 1最后一个元素一样简单.对于基于指针的表示,我们可以轻松确定是向左还是向右移动到最后一个元素.

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