在最大堆（假设它是由一个数组表示），该堆的顶部（即在堆的最大值）与阵列中的最后一个元素交换（即在堆的最小值中的一个），则最后一个元素被删除，然后用其他值的新顶级的堆元素互换定居回到自己适当的位置。
相反，为什么不是顶级元素只是删除，然后其他元素可以“填补”了堆？
Answer 1:
一个堆的关键特性是底层二叉树是完全二叉树（即每一级除了最后一个必须完全“装”）。 这是使堆有O(lg N)操作，因为我们只有在每个来修改一个元素O(lg N)的水平。 让我们看一个例子
10
/ \
8 7
/ \ / \
5 6 4 3
如果我们按照你的方法和“填充”我们得到了堆
8
/ \
6 7
/ \ / \
5 ? 4 3
树不再是一个完全二叉树是有“洞”的? 。 因为我们不知道树是完整的，我们不知道树的高度，任何东西，所以我们不能保证O(lg N)操作。
这就是为什么我们把最后一个元素在人堆里，把它放在顶部，然后将它洗下来 - 保持完全二叉树财产。
Answer 2:
为什么不是顶级元素只是删除，然后其他元素可以“填补”了堆？
这样做的原因是，一个元素的索引在维持堆的结构具有重要作用。 在索引的元素的两个孩子i位于索引2*i+1和2*i+2 。 如果你“只是删除”的顶级元素，你就不会与其他堆结束：索引1和2将不再包含的孩子max因素，因为max因素将不再存在。 从某种意义上说，你最终将有两个“破”堆而不是正常的。 您必须在指标零替换值，否则剩余元件之间的索引方案是要打破。
虽然从顶部移除元素不能被忽视，去掉一个在底部是确定：所有你需要做的是要记，最小的元素是在last-1 ，而不是last 。 所以操作的顺序变为如下：
- 删除可以安全移除的元素
- 其放回原处无法安全删除元素
- 下渗堆元素，直到它落户，采摘它的两个亲本高出每一步
Answer 3:
从概念上讲，你提出会正常工作。 堆的抽象定义允许最上面的元件被去除的其他于“过筛向上”。
在实践中，一个共同的堆实现通过使用连续的指针数组（当元素n的父位于位置n / 2）模拟一个树。 在此实现，这是不方便的指针数组中留下“空洞”。
“招”来解决这个问题是交换式的最后一个元素，并用“筛下”一步重新定位它。 这确保了所有连续数组元素是树的一部分，并且有在序列中没有孔。 这使得算法更容易实现，节省这将通过链接区所需要的空间。
内容提要 ：它仅仅是一个实现细节（很方便，也很常见）。
Answer 4:
堆算法的整体思路是，在任何时候你保持元素的完整树（由数组表示）。 如果从树的根目录中删除的东西，你必须把别的东西在里面吧。 在阵列最有效的方式来实现这是最后一个元素出现移动。
您的关注似乎是基于以下假设：在阵列（在树的叶元素）的最后一个元素是最小的元素。 这是不正确的。 堆阵列没有完全排序。 堆在每个子树“垂直”的排序，但它有子树之间没有“水平”排序。 阵列中的最后一个元素肯定会在从根到该叶唯一路径最小，但在一般情况下，它不会在整个堆的最小。
当你看的大小堆的任何叶元素N ，可以肯定地说，这不是一个log N在整个堆的最大因素。 但是，这一切都可以说。 例如，如果你的树中有256个元素，那么阵列（或任何其他叶元素）的最后一个元素将某处9日之间对排名第256。 看到？ 这可能是第九届了256个！ 参照这样的元素作为“最小的”仅仅是荒谬的。 平均而言，它不仅是不是最小的，它甚至还没有接近是最小的。
同样，最后一个元素被专门选择，因为它是保持连续的阵列最便宜的方式。 如果你在一些其他的方式来实现堆说，通过链接树，而不是一个数组，然后恢复堆根取出后可能会有所不同的最佳方式。
文章来源: Why does heapify swap the top of the heap with the element at the bottom of the heap?
