为什么堆树总是完整的二叉树或者几乎完全的二叉树？

Question

这是必要条件吗？或者我们能有这样的小堆吗？

     2
    / \
   5   6
      / \
     8   11

Answer 1

二进制堆可以(而且通常是)实现为数组，并按级别顺序列出值。只有当树是一棵(几乎)完整的树时，这个数组才没有“空白”。对于您已经给出的示例，相应的数组表示应该是：

[2, 5, 6, null, null, 8, 11]

这些null值很烦人，对插入/删除算法有影响。

在标准情况下(没有null)，这些算法可以很容易地通过检查相应的索引超出范围来判断节点的子节点数。现在，他们必须检查这些索引是否可能引用null值。

使用值遍历树的算法必须考虑将null更改为该值的可能性，而在树上携带值的算法必须考虑需要删除跟踪null值(以保持树的效率)。这些只是将要发生的额外并发症中的一部分。这是可能的，但只是减缓了这一过程。

最后，如果树的高度不被优化，那么它会使进程变慢，并且一些从根到叶的路径比在一棵(几乎)完整的树中长。