algorithm - 从 O(n * log(log(n))) 中的最大堆构建排序列表？

Question

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

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

我的回答:不，我们不能!我们总是可以在 A 上运行并在 O(n*log(n)) 中执行 MergeSort或 O(n*log(n)) 中的快速排序(最坏情况 O(n^2))。

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

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

Answer 1

我认为这是不可能的:有一种算法可以在 o(n) 中构建最大堆(看这里 Is there a O(n) algorithm to build a max-heap? )因此，如果您可以在 o(n) 中创建一个堆，然后在 o(nlog(log(n)) 中对其进行排序，你可以获得一个在 o(nlog(log(n)) 中工作的排序算法，如果你没有关于输入的初始信息，这是不可能的。