我有一个用数组 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)))
的任何选项,有什么想法吗?
最佳答案
我认为这是不可能的: 有一种算法可以在 o(n) 中构建最大堆(看这里 Is there a O(n) algorithm to build a max-heap? ) 因此,如果您可以在 o(n) 中创建一个堆,然后在 o(nlog(log(n)) 中对其进行排序, 你可以获得一个在 o(nlog(log(n)) 中工作的排序算法,如果你没有关于输入的初始信息,这是不可能的。
关于algorithm - 从 O(n * log(log(n))) 中的最大堆构建排序列表?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11155698/