chr*_*rds 2 heap data-structures
我一直在教自己考试,并遇到了以下问题:
"给出以下二元树不是堆的两个不同原因"
91 / \ 77 46 / \ \ 68 81 11
我知道其中一个原因是因为堆的子项必须小于或等于其父项的值,因此81违反此规则81 > 77,但我不确定另一个答案.
81
81 > 77
有人可以澄清一下吗？
Duk*_*ing 5
11应该是左孩子46,而不是右孩子.
11
46
维基百科提到二进制堆应该是一个完整的二叉树,这意味着"每个级别,除了可能是最后一个,完全填充,并且所有节点都尽可能地离开 ",显然不是这样的情况,如果11它在哪里现在.
这有利的原因相当容易理解 - 考虑到堆的大小,您可以快速确定底层最后一个节点的位置,这对于插入和删除是必要的.如果我们使用数组表示,它就像heap size - 1最后一个元素一样简单.对于基于指针的表示,我们可以轻松确定是向左还是向右移动到最后一个元素.
heap size - 1
如果堆不是完整的二叉树,可能还有其他方法可以获得相同的性能,但它们可能会增加复杂性.
归档时间：
11 年，6 月 前
查看次数：
624 次
最近记录：