在min堆中插入节点，末尾为空值。

Question

我得到了一个排序的最小堆数组：2,3,4,5,NULL

我想在其中插入值1，第一步将如何处理？

       2                     2
    /     \                /  \
   3       4   or this?   3    4
  / \      /             / \   
 5   NULL 1             5   1

如果节点是空的，情况会是相同的吗？

Answer 1

整数堆没有NULL值。我认为NULL表示堆的容量，这意味着它在满之前只能有一个额外的值。

如果节点是空的，

会是相同的吗？

尽管这种表示形式很不寻常，但除了节点是空的以外，NULL没有其他任何意义。如果将其视为数据，则存在不一致性。堆中的值所使用的数据类型应该是一致的和可比较的。因此，NULL不是数据的选择。

当您插入下一个值时，应该使用第一个空槽。然后它应该被筛选到正确的位置。

因此，来自：

     2
    / \
   3   4
  / \     
 5   NULL

至

     2
    / \
   3   4
  / \
 5   1

至

     1
    / \
   2   4
  / \     
 5   3

顺便说一句：“分类堆”不是一件事。是的，排序列表也是堆，但是堆的强大功能是它不需要总是被排序。它只保证堆属性，即父节点永远不会大于其子节点。