heap - 对堆的澄清——它们是否必须被填充才能成为有效的堆？

Question

阿卡

     1
2          3

是一个有效的堆吗？

然而

    1
2     

是不是，因为树没有在所有级别上填满？

或者堆的结构属性是否只指定堆只是被填充，使得在级别顺序的元素之间没有“间隙”。这意味着第二个堆也是有效堆吗？

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

所以

           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