简要背景：我正在研究在插入时维护堆属性的步骤。这是一个有趣的问题：
问题：可以使用两种常规策略来维护堆属性：
确保树是完整的，然后修复顺序或
首先确保订购正确，然后检查完整性。
哪个更好（1或2）？
参考：约翰·埃德加（John Edgar）博士撰写的http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf（堆插入-幻灯片16）。
如果你们能弄清楚为什么上述方法之一更好，那将是很好的选择？
最佳答案
通过将二进制堆实现为数组，通常有两种方法可以实现插入：自顶向下或自底向上。链接的PDF的幻灯片17描述了自下而上的处理方式。它将新项添加到堆的末尾（最底部，最左侧位置），并将其冒泡。这是幻灯片16所示的策略1的实现。
从性能的角度来看，这是一种更好的方法，仅因为平均而言，它需要较少的迭代来固定顺序。有关原因的详细说明，请参见Argument for O(1) average-case complexity of heap insertion。
自上而下的方法（对应于幻灯片16的策略2）要求每个插入都进行O（log n）比较。该策略从根开始，然后通过堆向下筛选项目。如果新项目小于（在最小堆中）与要比较的节点相比，它将替换该节点上的项目，而刚被替换的项目必须向下推。这一直持续到您到达堆的底部为止。没有“提前淘汰”的可能，因为您必须最终在叶子级别将新项放入堆中。
我从来没有真正想到过要先确定顺序，然后确保完整性，但这实际上就是自顶向下方法的工作。
第二种策略是每次插入需要更多的迭代，并且在每次迭代期间还需要做更多的工作来维持排序。