1

配列Aで表される最大ヒープがあり、次の質問があります。

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

私の答え：いいえ、できません！いつでもAMergeSortin O(n*log(n)) またはQuickSortin O(n*log(n))（最悪の場合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）にヒープを作成できれば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 に答える