配列A
で表される最大ヒープがあり、次の質問があります。
Is it possible to build a sorted list , based on the maximum
heap - A - in O(n*log(log(n))) ?
私の答え:いいえ、できません!いつでもA
MergeSortin O(n*log(n))
またはQuickSortin O(n*log(n))
(最悪の場合O(n^2)
)で実行して実行できます。
また、に基づいて実際のヒープを構築することも考えましたA
。これには、が必要O(n)
であり、そこからすべての要素を抽出しますがO(n*log(n))
、ここでは何も得られませんでした。
現時点では、オプションが表示されませんO(n*log(log(n)))
。アイデアはありますか?