1

我有一个数组中表示的最大堆A，我有以下问题：

Is it possible to build a sorted list , based on the maximum 
heap - A - in O(n*log(log(n))) ?

我的回答：不，我们不能！我们总是可以继续运行A并执行 MergeSort in O(n*log(n)) 或 QuickSort in O(n*log(n))(worst case O(n^2))。

我还想也许要建立实际的堆A，这需要O(n)，然后从那里提取所有元素O(n*log(n))，但我在这里一无所获。

目前我看不到任何选项O(n*log(log(n)))，任何想法？

4

2 回答 2

6

我认为这是不可能的：有一个算法可以在 o(n) 中构建一个最大堆（看看这里有一个 O(n) 算法来构建一个最大堆吗？）所以如果你可以在 o( n) 然后在 o(n log(log(n)) 中排序，你可以得到一个在 o(n log(log(n)) 中工作的排序算法，如果你没有关于你的初始信息，这是不可能的输入。

于 2012-06-22T12:33:11.997 回答
2

如果您有一个数组形式的最大堆，那么在该数组上使用诸如插入排序之类的东西应该会产生非常好的结果。数组形式的最大堆几乎已排序（降序），当数组几乎已排序时，插入的最佳情况是 O(n)。它仍然会有 O(n^2) 最坏的情况，但我认为你不会遇到最坏的情况。

于 2012-06-22T14:43:06.680 回答