3

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

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

4

4 回答 4

6

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

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

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

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

这棵树不再是一棵完整的二叉树，因为?. 由于我们不知道这棵树是否完整，因此我们对树的高度一无所知，因此无法保证O(lg N)操作。

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

于 2012-07-14T23:52:32.420 回答
4

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

原因是元素的索引在维护堆结构方面起着重要作用。index 处元素的两个子元素i位于 index2*i+1和2*i+2。如果您“只是删除”顶部元素，您将不会得到另一个堆：索引1并且2不再包含该元素的子max元素，因为该max元素将不再存在。从某种意义上说，你最终会得到两个“损坏”的堆，而不是一个正常工作的堆。您必须替换索引零处的值，否则其余元素之间的索引方案将崩溃​​。

虽然从顶部删除一个元素不会被忽视，但删除底部的元素是可以的：您需要做的就是记下最小的元素是 atlast-1而不是last. 所以操作顺序变成如下：

  • 移除可以安全移除的元素
  • 将它放在无法安全移除的元素的位置
  • 将元素向下渗透到堆中，直到它稳定下来，在每一步中选择它的两个父元素中的较高者
于 2012-07-14T23:59:45.967 回答
2

从概念上讲，您的建议可以正常工作。堆的抽象定义允许将最顶部的元素移除另一个以“筛选”。

在实践中，常见的堆实现通过使用连续指针数组来模拟树（当元素n的父元素位于位置n/2时）。在这个实现中，在指针数组中留下“洞”是不方便的。

解决该问题的“技巧”是交换最后一个元素并通过“筛选”步骤重新定位它。这确保了所有连续的数组元素都是树的一部分，并且序列中没有空洞。这使得算法更容易实现并节省链接字段所需的空间。

执行摘要：它只是一个实现细节（非常方便且非常常见）。

于 2012-07-14T23:53:09.920 回答
1

堆算法的整个想法是，始终保持完整的元素树（由数组表示）。如果您从树的根部删除了某些东西，则必须在其中放置其他东西。在数组中，实现这一目标的最有效方法是将最后一个元素移到那里。

您的担忧似乎是基于数组中的最后一个元素（树中的叶元素）是最小元素的假设。这是不正确的。堆数组未完全排序。堆在每个子树中都有“垂直”排序，但在子树之间没有“水平”排序。数组中的最后一个元素肯定是从根到叶的唯一路径中的最小元素，但一般情况下它不会是整个堆中的最小元素。

当您查看大小为 的堆的任何叶元素时N，您可以肯定地说它不是整个堆中log N 最大的元素之一。但这就是你能说的。例如，如果您的树中有 256 个元素，那么数组中的最后一个元素（或任何其他叶元素）将排在第 9 到第 256 之间。看？它可能是 256 个中的第 9 个！将这样的元素称为“最小”简直是荒谬的。平均而言，它不仅不是最小的，甚至还不是最小的。

同样，最后一个元素是专门选择的，因为它是维护连续数组的最便宜的方式。如果您以其他方式实现堆，例如通过链接树而不是数组，那么在根删除后恢复堆的最佳方式可能会有所不同。

于 2012-07-14T23:50:21.093 回答