algorithm - 移除最小元素后重新调整二叉堆

Question

删除二进制堆中的最小元素后，即删除根后，我知道必须调整堆以保持堆属性。但这样做的首选方法似乎是将最后一片叶子分配给根并筛选它。

我想知道为什么我们不采用曾经是根的较小的孩子，而只是继续筛选所有的孩子？这不是相同数量的操作，那么为什么首选“assign-the-last-leaf-to-the-root-and-sift-down”方法？

Answer 1

因为您必须从最后一行的左侧填充树。从上到下筛选，您不能保证您向上筛选的最后一个元素将是最右边的元素。