从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并执行MergeSort O(n*log(n))或QuickSort .O(n*log(n))O(n^2)

我想也许可以构建基于的实际堆A,这将采取O(n),然后从中提取所有元素O(n*log(n)),但我在这里没有获得任何东西.

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

Answer 1

我认为这是不可能的:有一种算法可以在o(n)中构建一个最大堆(看这里是否有一个O(n)算法来构建一个最大堆？)所以如果你可以在o中建立一个堆( n)然后在o(n log(log(n))中对它进行排序,你可以得到一个在o(n log(log(n))中工作的排序算法,如果你没有关于你的初始信息,这是不可能的输入.