在最大堆中（假设它由数组表示），堆顶（即堆中最大的值）与数组中的最后一个元素（即堆中最小的值之一）交换位置，然后移除最后一个元素，接着新的堆顶元素会与其他值交换位置以回到其正确的位置。
那么，为什么不直接移除堆顶元素，让其他元素“填补”堆呢？
那么，为什么不直接移除堆顶元素，让其他元素“填补”堆呢？
为什么堆排序要将堆顶和堆底元素交换？
5
- aerain
3
但将最后一个元素移动到顶部是一种“填充”已删除根元素的方法。您提出了什么其他类型的“填充”？您如何以任何其他方式在数组中“填充”？ - AnT stands with Russia
我无法确定你是懒得阅读还是其他原因。但是，最好再次复习理论，因为你显然在这里缺少基础。 - Alexander
@Alexander 或许“填充”这个词不太清晰，但从我所看到的两种主要答案中，它要么只是一个实现问题，要么他理解了堆属性但没有看到完全二叉树的要求。无论哪种方式，他似乎都理解了主要的堆属性，所以我认为这不是懒惰的表现。 - flight
4个回答
9
堆的关键属性之一是其底层的二叉树是一个完全二叉树（即每个除了最后一个层级必须完全“填满”）。这样，堆具有 O(lg N) 操作，因为我们只需要在每个 O(lg N) 层级修改一个元素。让我们看一个例子。
10
/ \
8 7
/ \ / \
5 6 4 3
如果按照您的方法并且“填充”堆栈，我们得到：
8
/ \
6 7
/ \ / \
5 ? 4 3
树不再是完全二叉树，因为在“?”处有一个“空洞”。由于我们不知道树是否完整，所以我们对树的高度一无所知，因此无法保证O(lg N) 操作。
这就是为什么我们取堆中的最后一个元素，将其置于顶部，然后向下移动 - 以保持完全二叉树属性。
- flight
1
我觉得我表达问题的方式可能不够清晰。这正是我想问的，谢谢！ - aerain
4
为什么不直接删除顶部元素然后让其他元素“填补”堆呢？
这是因为元素的索引在维护堆结构方面起着重要作用。一个索引为i的元素的两个子元素位于索引2*i+1和2*i+2处。如果你“只是删除”了顶部元素，你不会得到另一个堆：索引1和2将不再包含最大元素的子元素，因为最大元素不再存在。从某种意义上说，你会得到两个“破碎”的堆，而不是一个正常工作的堆。必须替换索引零处的值，否则剩余元素之间的索引关系会崩溃。
虽然从顶部删除元素可能无法逃脱注意，但从底部删除元素是可以的：你需要做的只是记下最小元素在last-1处而不是last处。所以操作序列变成了以下几步：
- 删除可以安全删除的元素 - 将其放置在无法安全删除的元素的位置 - 将元素向下移动，直到它安定下来，在每个步骤中选择其两个父元素中更高的一个。
这是因为元素的索引在维护堆结构方面起着重要作用。一个索引为i的元素的两个子元素位于索引2*i+1和2*i+2处。如果你“只是删除”了顶部元素，你不会得到另一个堆：索引1和2将不再包含最大元素的子元素，因为最大元素不再存在。从某种意义上说，你会得到两个“破碎”的堆，而不是一个正常工作的堆。必须替换索引零处的值，否则剩余元素之间的索引关系会崩溃。
虽然从顶部删除元素可能无法逃脱注意，但从底部删除元素是可以的：你需要做的只是记下最小元素在last-1处而不是last处。所以操作序列变成了以下几步：
- 删除可以安全删除的元素 - 将其放置在无法安全删除的元素的位置 - 将元素向下移动，直到它安定下来，在每个步骤中选择其两个父元素中更高的一个。
- Sergey Kalinichenko
3
从概念上讲，您提出的方案完全可行。堆的抽象定义允许删除顶部元素并将其他元素“筛选向上”。
在实践中，一种常见的堆实现通过使用连续指针数组来模拟树（当元素n的父级位于位置n/2时）。在此实现中，在指针数组中留下“空洞”是不方便的。
解决该问题的“技巧”是交换最后一个元素，并使用“筛选向下”步骤重新定位它。这确保了所有连续的数组元素都是树的一部分，并且序列中没有空洞。这使算法更易于实现，并节省了链接字段所需的空间。
执行摘要：这只是一些实现细节（非常方便和非常普遍）。
在实践中，一种常见的堆实现通过使用连续指针数组来模拟树（当元素n的父级位于位置n/2时）。在此实现中，在指针数组中留下“空洞”是不方便的。
解决该问题的“技巧”是交换最后一个元素，并使用“筛选向下”步骤重新定位它。这确保了所有连续的数组元素都是树的一部分，并且序列中没有空洞。这使算法更易于实现，并节省了链接字段所需的空间。
执行摘要：这只是一些实现细节（非常方便和非常普遍）。
- Raymond Hettinger
1
堆算法的整个思想是始终保持元素的完整树（由数组表示）。如果从树的根部删除了某些内容，则必须将其他内容放入其中。在数组中，实现这一点最有效的方法是将最后一个元素移动到那里。
您的担忧似乎基于这样的假设：数组中的最后一个元素（树中的叶子元素）是最小的元素。这是不正确的。堆数组没有完全排序。堆在每个子树中具有“垂直”排序，但在子树之间没有“水平”排序。数组中的最后一个元素肯定是从根到该叶子节点的唯一路径中最小的，但在一般情况下，它不会是整个堆中最小的。
您的担忧似乎基于这样的假设：数组中的最后一个元素（树中的叶子元素）是最小的元素。这是不正确的。堆数组没有完全排序。堆在每个子树中具有“垂直”排序，但在子树之间没有“水平”排序。数组中的最后一个元素肯定是从根到该叶子节点的唯一路径中最小的，但在一般情况下，它不会是整个堆中最小的。
当你看着堆的大小为N的任何叶子元素时，你可以肯定地说它不是整个堆中最大的log N个元素之一。但这就是你能说的全部。例如，如果你的树有256个元素，那么数组中的最后一个元素（或任何其他叶子元素）将在第9到第256位之间。明白了吗？它可能是256个元素中的第9个！把这样的元素称为“最小”的简直是荒谬的。平均而言，它不仅不是最小的，甚至离最小都很遥远。
同样，选择最后一个元素只是因为它是维护连续数组的最便宜的方式。如果你以其他方式实现了堆，比如通过链表树而不是数组，那么在移除根节点后恢复堆的最优方式可能会有所不同。
- AnT stands with Russia
1
能否从堆的底层选择一个不是最右边元素的元素？这样做仍然可以保持堆的属性，对吗？ - information_interchange
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接