c++ - 维护堆属性

Question

• 简要背景:我正在研究插入发生时维护堆属性的步骤。这是一个有趣的问题:

• 问题:有两种通用策略可用于维护堆属性:

  1. 确保树是完整的，然后修复排序或
  2. 首先确保顺序正确，然后检查完​​整性。

哪个更好(1 或 2)？

引用:http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf (堆插入 - 幻灯片 16)由 John Edgar 博士撰写。

如果你们能阐明为什么上述方法之一更好，那就太好了？

Answer 1

将二叉堆实现为数组，通常有两种实现插入的方法:自上而下或自下而上。链接 PDF 的幻灯片 17 描述了自下而上的做事方式。它将新项目添加到堆的末尾(最底部、最左侧的位置)，并将其向上冒泡。这是幻灯片 16 中显示的策略 1 的实现。

从性能的角度来看，这是更好的方法，因为平均，它需要更少的迭代来修复排序。参见 Argument for O(1) average-case complexity of heap insertion详细解释为什么会这样。

自上而下的方法，对应于幻灯片 16 上的策略 2，要求每次插入都进行 O(log n) 比较。该策略从根开始，通过堆向下筛选项目。如果新项小于(在最小堆中)与它进行比较的节点，它会替换该节点上的项，并且必须下推刚刚替换的项。这一直持续到您到达堆的底部。不存在“提前退出”的可能，因为您最终必须在叶级将新项目放入堆中。

我从来没有真正认为它是先确保顺序，然后再确保完整性，但这基本上就是自上而下方法所做的事情。

第二种策略每次插入需要更多的迭代，并且在每次迭代期间也做更多的工作来维持顺序。