如何构建堆的时间复杂度为 O(n)? [英] How can building a heap be O(n) time complexity?

问题描述

有人可以帮助解释如何构建一个O(n)复杂度的堆吗?

向堆中插入项是O(log n)，插入重复n/2次(剩余的是叶子，不能违反堆属性).所以，这意味着复杂度应该是 O(n log n)，我想.

换句话说，对于我们堆化"的每个项目，到目前为止，它有可能必须对堆的每个级别(即log n 级别).

我错过了什么?

解决方案

我觉得这个话题有几个问题:

• 您如何实现 buildHeap 以使其在 O(n) 时间内运行?
• 你如何证明 buildHeap 在正确实现的情况下在 O(n) 时间内运行?
• 为什么相同的逻辑不能使堆排序在 O(n) 时间内运行，而不是 O(n log n)?

你如何实现 buildHeap 使其在 O(n) 时间内运行?

通常，这些问题的答案集中在siftUp 和siftDown 之间的区别上.在 siftUp 和 siftDown 之间做出正确的选择对于获得 buildHeap 的 O(n) 性能至关重要，但是没有什么可以帮助人们理解 buildHeap 和 heapSort 之间的一般区别.实际上，buildHeap 和 heapSort 的正确实现将仅使用 siftDown.siftUp 操作只需要执行插入到现有堆的操作，因此它将用于使用二进制堆实现优先级队列，例如.

我写这篇文章是为了描述最大堆的工作原理.这是通常用于堆排序或优先级队列的堆类型，其中较高的值表示较高的优先级.最小堆也很有用；例如，在检索具有升序整数键或按字母顺序的字符串的项目时.原理完全一样；只需切换排序顺序即可.

堆属性指定二叉堆中的每个节点必须至少与其两个子节点一样大.特别是，这意味着堆中最大的项目位于根.向下筛选和向上筛选本质上是相反方向的相同操作:移动违规节点，直到它满足堆属性:

• siftDown 将一个太小的节点与其最大的子节点交换(从而将其向下移动)，直到它至少与它下面的两个节点一样大.
• siftUp 将一个太大的节点与其父节点交换(从而将其向上移动)，直到它不大于其上方的节点.

siftDown 和 siftUp 所需的操作次数与节点可能必须移动的距离成正比.对于siftDown，它是到树底部的距离，所以siftDown对于树顶部的节点来说是昂贵的.使用 siftUp，工作量与到树顶的距离成正比，所以 siftUp 对于树底的节点来说开销很大.尽管在最坏的情况下这两种操作都是O(log n)，但在堆中，只有一个节点位于顶部，而一半的节点位于底部.所以如果我们必须对每个节点应用一个操作，我们更喜欢 siftDown 而不是 siftUp 也就不足为奇了.>

buildHeap 函数接受一个未排序项的数组并移动它们直到它们都满足堆属性，从而产生一个有效的堆.使用我们描述的 siftUp 和 siftDown 操作，可以对 buildHeap 采取两种方法.

1. 从堆的顶部(数组的开头)开始，并对每个项目调用 siftUp.在每一步，先前筛选的项目(数组中当前项目之前的项目)形成一个有效的堆，向上筛选下一个项目会将其放置在堆中的有效位置.筛选出每个节点后，所有项都满足堆属性.

2. 或者，向相反的方向走:从数组的末尾开始，向后向前移动.在每次迭代中，您都会筛选一个项目，直到它位于正确的位置.

buildHeap 哪种实现更有效?

这两种解决方案都会产生一个有效的堆.不出所料，效率更高的是使用 siftDown 的第二个操作.

让 h = log n 代表堆的高度.siftDown 方法所需的工作由总和给出

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

总和中的每一项都具有给定高度的节点必须移动的最大距离(底层为零，根为 h)乘以该高度的节点数.相比之下，每个节点上调用siftUp的总和为

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

应该清楚，第二个和更大.仅第一项是hn/2 = 1/2 n log n，因此这种方法的复杂度至多O(n log n).

我们如何证明 siftDown 方法的总和确实是 O(n)?

一种方法(也有其他分析方法)是将有限和转化为无限级数，然后使用泰勒级数.我们可以忽略第一项，它为零:

如果您不确定为什么每个步骤都有效，以下是该过程的文字说明:

• 各项都是正数，因此有限和必须小于无限和.
• 该级数等于在 x=1/2 处评估的幂级数.
• 那个幂级数等于(常数倍)泰勒级数的导数，f(x)=1/(1-x).
• x=1/2 在那个泰勒级数的收敛区间内.
• 因此，我们可以将泰勒级数替换为1/(1-x)，进行微分和求值以找到无穷级数的值.

由于无限和正好是 n，我们得出结论，有限和并不更大，因此是 O(n).

为什么堆排序需要O(n log n)时间?

如果可以在线性时间内运行 buildHeap，为什么堆排序需要 O(n log n) 时间?好吧，堆排序由两个阶段组成.首先，我们在数组上调用 buildHeap，如果实现最佳，则需要 O(n) 时间.下一步是重复删除堆中最大的项目并将其放在数组的末尾.因为我们从堆中删除了一个项目，所以在堆的末尾总是有一个空位可以存储该项目.所以堆排序通过依次删除下一个最大的项并将其放入数组中，从最后一个位置开始并向前移动来实现排序顺序.在堆排序中占主导地位的是最后一部分的复杂性.循环看起来像这样:

for (i = n - 1; i > 0; i--) {arr[i] = deleteMax();}

显然，循环运行 O(n) 次(n - 1 准确地说，最后一项已经就位).堆的deleteMax 复杂度是O(log n).它通常通过移除根(堆中剩余的最大项)并将其替换为堆中的最后一项，即叶，因此是最小项之一来实现.这个新根几乎肯定会违反堆属性，因此您必须调用 siftDown 直到将其移回可接受的位置.这也具有将下一个最大的项目向上移动到根的效果.请注意，与 buildHeap 不同的是，对于大多数我们从树底部调用 siftDown 的节点，我们现在调用 siftDown从每次迭代的树顶开始！虽然树在缩小，但它缩小得不够快:树的高度保持不变，直到您移除前半部分节点(当您完全清除底层时).然后对于下一个季度，高度为 h - 1.所以第二阶段的总工作量是

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

注意切换:现在零工况对应于单个节点，而 h 工况对应于一半的节点.这个总和是O(n log n)，就像使用 siftUp 实现的 buildHeap 的低效版本一样.但在这种情况下，我们别无选择，因为我们正在尝试排序，我们需要接下来删除下一个最大的项目.

总而言之，堆排序的工作是两个阶段的总和:O(n) 时间构建堆和 O(n log n) 按顺序删除每个节点，所以复杂度是 O(n log n).您可以证明(使用信息论中的一些想法)对于基于比较的排序，O(n log n) 无论如何都是您希望的最佳结果，因此没有理由对此感到失望或者期望堆排序能够达到 buildHeap 所做的 O(n) 时间限制.

Can someone help explain how can building a heap be O(n) complexity?

Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the heap property). So, this means the complexity should be O(n log n), I would think.

In other words, for each item we "heapify", it has the potential to have to filter down (i.e., sift down) once for each level for the heap so far (which is log n levels).

What am I missing?

解决方案

I think there are several questions buried in this topic:

• How do you implement buildHeap so it runs in O(n) time?
• How do you show that buildHeap runs in O(n) time when implemented correctly?
• Why doesn't that same logic work to make heap sort run in O(n) time rather than O(n log n)?

How do you implement buildHeap so it runs in O(n) time?

Often, answers to these questions focus on the difference between siftUp and siftDown. Making the correct choice between siftUp and siftDown is critical to get O(n) performance for buildHeap, but does nothing to help one understand the difference between buildHeap and heapSort in general. Indeed, proper implementations of both buildHeap and heapSort will only use siftDown. The siftUp operation is only needed to perform inserts into an existing heap, so it would be used to implement a priority queue using a binary heap, for example.

I've written this to describe how a max heap works. This is the type of heap typically used for heap sort or for a priority queue where higher values indicate higher priority. A min heap is also useful; for example, when retrieving items with integer keys in ascending order or strings in alphabetical order. The principles are exactly the same; simply switch the sort order.

The heap property specifies that each node in a binary heap must be at least as large as both of its children. In particular, this implies that the largest item in the heap is at the root. Sifting down and sifting up are essentially the same operation in opposite directions: move an offending node until it satisfies the heap property:

• siftDown swaps a node that is too small with its largest child (thereby moving it down) until it is at least as large as both nodes below it.
• siftUp swaps a node that is too large with its parent (thereby moving it up) until it is no larger than the node above it.

The number of operations required for siftDown and siftUp is proportional to the distance the node may have to move. For siftDown, it is the distance to the bottom of the tree, so siftDown is expensive for nodes at the top of the tree. With siftUp, the work is proportional to the distance to the top of the tree, so siftUp is expensive for nodes at the bottom of the tree. Although both operations are O(log n) in the worst case, in a heap, only one node is at the top whereas half the nodes lie in the bottom layer. So it shouldn't be too surprising that if we have to apply an operation to every node, we would prefer siftDown over siftUp.

The buildHeap function takes an array of unsorted items and moves them until they all satisfy the heap property, thereby producing a valid heap. There are two approaches one might take for buildHeap using the siftUp and siftDown operations we've described.

1. Start at the top of the heap (the beginning of the array) and call siftUp on each item. At each step, the previously sifted items (the items before the current item in the array) form a valid heap, and sifting the next item up places it into a valid position in the heap. After sifting up each node, all items satisfy the heap property.

2. Or, go in the opposite direction: start at the end of the array and move backwards towards the front. At each iteration, you sift an item down until it is in the correct location.

Which implementation for buildHeap is more efficient?

Both of these solutions will produce a valid heap. Unsurprisingly, the more efficient one is the second operation that uses siftDown.

Let h = log n represent the height of the heap. The work required for the siftDown approach is given by the sum

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Each term in the sum has the maximum distance a node at the given height will have to move (zero for the bottom layer, h for the root) multiplied by the number of nodes at that height. In contrast, the sum for calling siftUp on each node is

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

It should be clear that the second sum is larger. The first term alone is hn/2 = 1/2 n log n, so this approach has complexity at best O(n log n).

How do we prove the sum for the siftDown approach is indeed O(n)?

One method (there are other analyses that also work) is to turn the finite sum into an infinite series and then use Taylor series. We may ignore the first term, which is zero:

If you aren't sure why each of those steps works, here is a justification for the process in words:

• The terms are all positive, so the finite sum must be smaller than the infinite sum.
• The series is equal to a power series evaluated at x=1/2.
• That power series is equal to (a constant times) the derivative of the Taylor series for f(x)=1/(1-x).
• x=1/2 is within the interval of convergence of that Taylor series.
• Therefore, we can replace the Taylor series with 1/(1-x), differentiate, and evaluate to find the value of the infinite series.

Since the infinite sum is exactly n, we conclude that the finite sum is no larger, and is therefore, O(n).

Why does heap sort require O(n log n) time?

If it is possible to run buildHeap in linear time, why does heap sort require O(n log n) time? Well, heap sort consists of two stages. First, we call buildHeap on the array, which requires O(n) time if implemented optimally. The next stage is to repeatedly delete the largest item in the heap and put it at the end of the array. Because we delete an item from the heap, there is always an open spot just after the end of the heap where we can store the item. So heap sort achieves a sorted order by successively removing the next largest item and putting it into the array starting at the last position and moving towards the front. It is the complexity of this last part that dominates in heap sort. The loop looks likes this:

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

Clearly, the loop runs O(n) times (n - 1 to be precise, the last item is already in place). The complexity of deleteMax for a heap is O(log n). It is typically implemented by removing the root (the largest item left in the heap) and replacing it with the last item in the heap, which is a leaf, and therefore one of the smallest items. This new root will almost certainly violate the heap property, so you have to call siftDown until you move it back into an acceptable position. This also has the effect of moving the next largest item up to the root. Notice that, in contrast to buildHeap where for most of the nodes we are calling siftDown from the bottom of the tree, we are now calling siftDown from the top of the tree on each iteration! Although the tree is shrinking, it doesn't shrink fast enough: The height of the tree stays constant until you have removed the first half of the nodes (when you clear out the bottom layer completely). Then for the next quarter, the height is h - 1. So the total work for this second stage is

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Notice the switch: now the zero work case corresponds to a single node and the h work case corresponds to half the nodes. This sum is O(n log n) just like the inefficient version of buildHeap that is implemented using siftUp. But in this case, we have no choice since we are trying to sort and we require the next largest item be removed next.

In summary, the work for heap sort is the sum of the two stages: O(n) time for buildHeap and O(n log n) to remove each node in order, so the complexity is O(n log n). You can prove (using some ideas from information theory) that for a comparison-based sort, O(n log n) is the best you could hope for anyway, so there's no reason to be disappointed by this or expect heap sort to achieve the O(n) time bound that buildHeap does.

这篇关于如何构建堆的时间复杂度为 O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！