澄清堆-它们是否必须填充才能成为一个有效的堆？

Question

又名

     1
2          3

是一个有效的堆吗？

鉴于

    1
2     

难道不是，因为树没有在所有的层次上被填满吗？

还是堆的结构属性仅指定堆是刚刚填充的，这样就没有按级别顺序排列的元素之间的“空白”。意味着第二个堆也是一个有效的堆？

还是堆的结构属性只要求堆是满的，也就是每个父母都有0或两个孩子？

所以

           1
       2      3  
   4     7   9   99

是有效的堆，如下所示

           1
       2      3  
   4     7   

但不是

          1
       2      3  
   4     7   9   

Answer 1

这主要是一个关于术语的问题。但是，堆几乎总是被定义为根树，其中：

1. 对于除根节点以外的每个节点，其密钥不小于其父节点的密钥。
2. 每个节点都有0，1或2个子节点，并且
3. 树几乎是一个完整的二叉树，但可能是最后一个层次。最后一层应从左到右填写。

因此，这些是有效的堆：

        1                5
     2     3          9     8
   3  6   9         11

而这些并不是：

        1                5
     2                9     8
   3                   13  9 10