17

ヒープソートの最悪の場合の実行時間はΩ（nlg n）であることはよく知られていますが、これがなぜであるかを理解するのに苦労しています。特に、ヒープソートの最初のステップ（最大ヒープの作成）には時間Θ（n）がかかります。その後、n個のヒープが削除されます。各ヒープの削除に時間がかかる理由を理解していますO（lg n）; ヒープのリバランスには、ヒープの高さで時間O（h）を要するバブルダウン操作が含まれ、h = O（lg n）です。しかし、私にはわからないのは、この2番目のステップでΩ（n lg n）が必要な理由です。個々のヒープのデキューによって、必ずしもノードがツリーの一番下に移動したとは限らないようです。

私の質問は-ヒープソートの最良の振る舞いの良い下限の証拠を知っている人はいますか？

4

3 に答える 3

19

だから私は自分自身を少し掘り下げました、そしてこの結果は実際にはかなり最近のようです！ヒープソート自体は1964年に発明されましたが、私が見つけた最初の下限の証明は1992年のものです。

正式な下限の証明は、SchafferとSedgewickの「TheAnalysisofHeapsort」の論文によるものです。これは、技術的な詳細の一部を省略した、少し言い換えたバージョンの証明です。

まず、あるkに対してn = 2 k -1であると仮定します。これにより、完全なバイナリヒープが保証されます。このケースを個別に処理する方法については、後で説明します。2 k -1の要素があるため、ヒープソートの最初のパスは、Θ（n）で高さkのヒープを構築します。ここで、このヒープからのデキューの前半を考えてみましょう。これにより、2k-1が削除されます。ヒープからのノード。最初の重要な観察は、開始ヒープを取得し、実際にデキューされるすべてのノードをここでマークすると、それらはヒープのサブツリーを形成することです（つまり、デキューされるすべてのノードには、デキューされる親があります）。これが当てはまらない場合は、ノード自体がデキューされたにもかかわらず、（大きい）親がデキューされなかったノードが存在するため、これを確認できます。これは、値の順序が正しくないことを意味します。

ここで、このツリーのノードがヒープ全体にどのように分散されているかを考えてみましょう。ヒープのレベルに0、1、2、...、k-1のラベルを付けると、レベル0、1、2、...、k-2にこれらのノードがいくつか存在します（つまり、ツリーの最下位レベルを除くすべて）。これらのノードがヒープからデキューされるためには、ルートまでスワップアップする必要があり、一度に1レベルだけスワップアップされます。これは、ヒープソートの実行時間を下限にする1つの方法は、これらすべての値をルートに上げるために必要なスワップの数を数えることであることを意味します。実際、それがまさに私たちがやろうとしていることです。

答える必要のある最初の質問は、ヒープの最下位レベルにない最大の2k-1ノードの数です。矛盾により、これが2k-2以下であることを示すことができます。ヒープの最下位レベルに少なくとも2k-2 +1の最大ノードがあるとします。次に、これらのノードの各親は、レベルk-2の大きなノードである必要があります。最良の場合でも、これは、レベルk-2に少なくとも2つのk-3 +1つの大きなノードが存在する必要があることを意味します。レベルk-3などに少なくとも2つのk-4 +1つの大きなノードがあることを確認します。これらのノードすべてを合計すると、2 k-2 + 2 k-3 + 2k-4 +があることがわかります。 ... + 20 +kラージノード。ただし、この値は厳密に2 k-1を超えており、ここでは2k-1ノードのみを使用しているという事実と矛盾しています。

さて...これで、最下層に最大2k-2の大きなノードがあることがわかりました。これは、最初のk-2層に少なくとも2k-2の大きなノードが必要であることを意味します。ここで、これらのノードすべてにわたって、そのノードからルートまでの距離の合計はどれくらいかを尋ねます。ええと、完全なヒープのどこかに2つのk-2ノードが配置されている場合、それらの最大2 k-3が最初のk-3レベルにある可能性があるため、少なくとも2k- 2-2k-があります。レベルk-2の3 =2 k-3ヘビーノード。したがって、実行する必要のあるスワップの総数は、少なくとも（k-2）2k-3です。n = 2kなので-1、k =Θ（lgn）であるため、この値は必要に応じてΘ（n lg n）になります。

于 2011-01-04T21:03:07.153 に答える
3

簡単な観察の答えはこれです：ヒープ内のアイテムは次のとおりです。

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

たとえば、7つのアイテムがある場合：

1
2
4

そしてあなたが8つのアイテムを持っているならば：

1
2
4
1

2つの異なるヒープツリーがあります。最初は少なくともn/4-ヒープの1つのアイテムが最後のレベルにあるかどうかに関係なく、n/4 - 1最後のレベルの前に少なくとも1つのアイテムがあります。最初のケースではO((n/4 - 1) * log(n/2))、最後のレベルのアイテムを削除する必要があります。ヒープから、そして2番目のケースではO((n/4 - 1) * log(n/4))、前の最後のレベルからアイテムを削除する必要があります。したがって、どちらの場合も、n / 4- 1アイテムの場合はΩ（nlog（n））が必要なので、下限になります（厳密な下限であると簡単に言えます）。

于 2011-01-04T07:58:10.670 に答える
1

CLRS用語を使用するソリューションは次のとおりです。要素を含む
完全なバイナリツリーであるmax-heapから始めます。完全なバイナリには、リーフと内部ノード があると言えます。ヒープから最大の要素を削除する反復。最大の要素のセットにし ましょう。内側のノードに要素が追加されている必要があるため、葉には 多くても要素が含まれている可能性があります。葉の中にあるこれらの最大の要素にし ましょう。 したがって、レベル0（葉のレベル）からの要素がある場合は、少なくともn
n/2n/2
n/2HEAP-SORTn/2
Sn/2
n/4Sn/4
Ln/4S
n/4Sn/8レベル1にあるこれらの要素とします
。HEAP -SORTを繰り返すと、ショートカットからルート、そしてヒープからの要素が得られる場合がありますが、からの要素は、ヒープから削除される前のルート。 したがって、少なくとも操作があり、実行時間はΩ（nlgn）になります。 ここ で、レベル0にすべての葉がない最大ヒープの場合。レベル0にある葉の数とします。HEAP-SORTを繰り返した 後、最大ヒープは次のようになります。高さのある完全な二分木。 同じように証明を続けることができます。Pn/8S
n/2LP
(n/8)(lgn-1)

k
klgn-1

n/4ここで、からの葉 が少ない場合について説明しSます。
レベル0の葉にあるk要素の数とします。その 場合、レベル1の要素が少なくとも存在する必要があります。これは、レベル1より上の要素 の合計が存在する可能性があるためです。 同じ方法で証明を続行します。 。 その場合、少なくともレベル1の要素が存在する必要があります 。同じ方法で証明を続行します。 HEAP-SORTの実行時間はΩ（nlgn）であると結論付けます。S
k <= n/8n/8S
n/4

k>n/8n/16S

于 2012-02-08T15:24:55.490 に答える