algorithm - 为什么heapify会交换堆顶元素和堆底元素？

Question

在最大堆(假设它由数组表示)中，堆的顶部(即堆中的最大值)与数组中的最后一个元素(即堆中的最小值之一)交换)，最后一个元素被移除，然后新的堆顶元素与其他值交换以回到其正确的位置。

相反，为什么不只是删除顶部元素，然后其他元素可以“填充”堆？

Answer 1

堆的一个关键属性是底层二叉树是一棵完整二叉树(即除了最后一层之外的每一层都必须完全“填充”)。这是为了使堆具有 O(lg N) 操作，因为我们只需要在每个 O(lg N) 级别修改一个元素。我们来看一个例子

    10
   /  \
  8    7
 / \  / \
5  6  4  3

如果我们按照您的方法“填充”我们得到的堆

     8
   /   \
  6     7
 / \   / \
5  ?   4  3

树不再是完整的二叉树，因为在 ? 处有一个“洞”。因为我们不知道树是否完整，所以我们不知道树的高度，所以我们不能保证 O(lg N) 操作。

这就是为什么我们取出堆中的最后一个元素，将其放在顶部然后将其打乱 - 以保持完整的二叉树属性。