1 
                             20
                           /    \
                          18     19
                        /   \   /  \   
                      10    13 15   1                      
                      /\    /\ 
                     5 9   8  11

上面是最大堆，它是一系列插入和删除最大操作后的结果。假设最后一个操作是插入。最后一次插入操作的可能键是什么？

我不确定的原因是因为这个问题没有说明它是否已经被堆化，所以它可以或不能已经被排序。但话又说回来，我可能错了。

附加问题：“删除最大操作”是否与“删除”相同，因为我之前没有遇到过这个术语，这有助于澄清我的困惑。

谢谢！

4

1 回答 1

3

插入二叉堆的方法是将项目放在堆的末尾，然后将其通过堆筛选到适当的位置。

因此，如果您显示的堆是最后一次插入操作之后的堆，那么在该插入开始时，堆必须只有 10 个项目。新项目现在放置在值 11 的位置。

如果该项目是从那里筛选出来的，那么它可能被筛选到的唯一位置就是现在数字 13、18 和 20 所在的位置。但是插入的数字不可能是 20，因为如果是，那么 18 将是堆的根，那将是无效的（因为 19 大于 18，因此 19 将是根）。

因此，最后插入的唯一可能值是 18、13 和 11。

在插入之前，树的那个分支可能是：

  • [18,13]: 添加 11 不需要任何交换。
  • [18,11]: 加 13 然后和 11 交换。
  • [13,11]：添加 18，然后将其与 11 交换，然后与 13
于 2018-05-03T14:52:02.123 回答