BUILD-MAX-HEAP运行时间降序排列

我知道BUILD-MAX-HEAP在堆排序中的运行时间为O(n)。但是，如果我们有一个已经按降序排序的数组，为什么在BUILD-MAX-HEAP的运行时间仍然有O(n)？
是不是应该像O(1)？它已经从最大值到最小值排序，所以我们不需要MAX-HEAPIFY。BUILD-MAX-HEAP运行时间降序排列

我的理解是否正确？有人可以向我解释吗？

来源

2016-09-25 mskeira

你说得对。它当然可以是O(1)。当你确定你的列表已经排序后，你可以使用它作为你的最大堆。

使用阵列的堆的共同实现使用这种行为它的元素的位置是：

childs[i] = 2i+1 and 2i+2 
parent[i] = floor((i-1)/2)

此规则应用于一个排序后的数组上。（下降为最大堆，增加最小堆）。

请note如果您需要先检查列表是否已排序，那当然仍然是O(n)。

编辑：堆排序复杂
即使阵列可能进行排序和构建堆实际上可能采取O(1)。无论何时执行堆排序，您仍然会以O(n log n)结束。
正如在评论中所说，堆排序正在执行n致电extract-max。每个提取操作需要O(log n) - 我们最终的总时间复杂度为O(n log n)。
如果数组未被排序，我们将得到总计时间复杂度为O(n + nlogn)，这仍然是O(n log n)。

来源

2016-09-25 21:59:31

谢谢你的回答。但是，即使BUILD-MAX-HEAP只花费时间“O（1）”，为什么堆排序仍然具有'O（n lg n）'的运行时间。为什么它不是'O（1 lg n）'='O（lg n）'？ – mskeira

@mskeira，因为执行堆排序的时间主要是* n *调用extract-max，即使堆初始完全排序，每个调用都需要** log ** * n *时间。有一些堆排序的变体实现在“接近排序”的输入上表现更好。 – rici

@mskeira我已经编辑了我的答案，因为它有点超出了问题的范围。如果你发现这个答案是正确的，请考虑通过点击我答案旁边的* V *来接受它。乐意效劳。 –

如果你知道该数组已经按降序排序，那么就没有必要对它进行排序。如果您希望按升序排列，则可以在O（n）时间内反转阵列。

如果您不知道数组是否已经排序，那么需要O（n）来确定它是否已经被反向排序。

从反向排序数组构建最大堆的原因被认为是O（n）是您必须从第n/2项开始，并且向后工作，确保该元素不小于其子元素。即使只有n/2次检查，也会将其视为O（n），因为执行的操作次数与要检查的项目总数成比例。

顺便提一下，有趣的是，您可以从反向排序数组中构建最大堆，而不是检查数组以查看是否进行了反向排序。

来源

2016-09-27 17:42:43

BUILD-MAX-HEAP运行时间降序排列

回答

相关问题