为什么heapify将堆顶部与堆底部的元素交换？

Question

在最大堆中(假设它由数组表示),堆的顶部(即堆中的最大值)与数组中的最后一个元素交换(即堆中最小值之一),删除最后一个元素,然后新的top-of-the-heap元素与其他值交换以恢复到正确的位置.

相反,为什么不删除顶部元素,然后其他元素可以"填充"堆？

Answer 1

堆的一个关键属性是底层二进制树是一个完整的二叉树(即除了最后一个之外的每个级别都必须完全"填充").这样堆就有了O(lg N)操作,因为我们只需修改每个O(lg N)级别的一个元素.我们来看一个例子吧

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

如果我们按照你的方法并"填写"我们得到的堆

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

树不再是完整的二叉树,因为树上有一个"洞" ?.由于我们不知道树是完整的,因此我们对树的高度一无所知,因此我们无法保证O(lg N)操作.

这就是为什么我们采用堆中的最后一个元素,将其置于顶部然后将其混洗 - 以维护完整的二叉树属性.