维护堆 属性
Maintaining Heap Property
简要背景：我正在研究发生插入时维护堆属性的步骤。这是一个有趣的问题：
问题：有两种通用策略可用于维护堆属性：
- 确保树是完整的，然后修复顺序或
- 首先确保顺序正确，然后检查完整性。
哪个更好（1 或 2）？
参考文献：http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf（堆插入 - 幻灯片 16）由 John Edgar 博士撰写。
如果你们能阐明为什么上述方法之一更好，那就太好了？
将二叉堆实现为数组，通常有两种实现插入的方式：自上而下或自下而上。链接 PDF 的幻灯片 17 描述了自下而上的做事方式。它将新项目添加到堆的末尾（最底部、最左侧的位置），并将其向上冒泡。这是幻灯片 16 中显示的策略 1 的实施。
从性能的角度来看，这是更好的方法，因为 平均而言，它需要更少的迭代来修复排序。请参阅 详细解释为什么会这样。
自上而下的方法，对应于幻灯片 16 上的策略 2，要求 每次插入都进行 O(log n) 次比较。该策略从根开始，通过堆筛选项目。如果新项小于（在最小堆中）与它进行比较的节点，它会替换该节点上的项，并且必须下推刚刚替换的项。这一直持续到您到达堆的底部。没有 "early out" 可能，因为您最终必须在叶级别的堆中放置一个新项目。
我从来没有真正认为它是先确保顺序，然后再确保完整性，但这基本上就是自上而下方法所做的。
第二种策略每次插入需要更多的迭代，并且在每次迭代期间也做更多的工作来保持顺序。
简要背景：我正在研究发生插入时维护堆属性的步骤。这是一个有趣的问题：
问题：有两种通用策略可用于维护堆属性：
- 确保树是完整的，然后修复顺序或
- 首先确保顺序正确，然后检查完整性。
哪个更好（1 或 2）？
参考文献：http://www.cs.sfu.ca/CourseCentral/225/johnwill/cmpt225_09heaps.pdf（堆插入 - 幻灯片 16）由 John Edgar 博士撰写。
如果你们能阐明为什么上述方法之一更好，那就太好了？
将二叉堆实现为数组，通常有两种实现插入的方式：自上而下或自下而上。链接 PDF 的幻灯片 17 描述了自下而上的做事方式。它将新项目添加到堆的末尾（最底部、最左侧的位置），并将其向上冒泡。这是幻灯片 16 中显示的策略 1 的实施。
从性能的角度来看，这是更好的方法，因为 平均而言，它需要更少的迭代来修复排序。请参阅
自上而下的方法，对应于幻灯片 16 上的策略 2，要求 每次插入都进行 O(log n) 次比较。该策略从根开始，通过堆筛选项目。如果新项小于（在最小堆中）与它进行比较的节点，它会替换该节点上的项，并且必须下推刚刚替换的项。这一直持续到您到达堆的底部。没有 "early out" 可能，因为您最终必须在叶级别的堆中放置一个新项目。
我从来没有真正认为它是先确保顺序，然后再确保完整性，但这基本上就是自上而下方法所做的。
第二种策略每次插入需要更多的迭代，并且在每次迭代期间也做更多的工作来保持顺序。