Heapsortの下限？

Question

Heapsortの最悪のランタイムはω（n Lg n）であることはよく知られていますが、なぜこれがなぜあるのかを見るのに苦労しています。特に、Heapsortの最初のステップ（Max Heapを作成）には時間θ（n）がかかります。次に、Nヒープの削除が続きます。各ヒープの削除に時間がかかる理由がわかります。ヒープのリバランスには、ヒープの高さに時間がかかるバブルダウン操作とh = o（lg n）が含まれます。しかし、私が見ていないのは、なぜこの2番目のステップがω（n lg n）を取るべきかということです。個々のヒープデキューが必ずしもノードが上部に移動してツリーをずっと泡立つとは限らないようです。

私の質問は、Heapsortの最高のケースの動作に対する良い下限の証拠を知っている人はいますか？

Answer 1

だから私は少し自分自身を掘り下げましたが、この結果は実際にはかなり最近のようです！ Heapsort自体が1964年に発明されましたが、私が見つけることができる最初の下限の証拠は1992年です。

正式な下限の証明は、シャッファーとセッジウィックの「Heapsortの分析」論文によるものです。これは、技術的な詳細の一部を省略する証明のわずかに言い換えられたバージョンです。

まず、n = 2と仮定しましょう^k -1 kの場合は、完全なバイナリヒープがあることを保証します。このケースを別々に処理する方法を後で説明します。 2つあるからです^k -1つの要素、heapsortの最初のパスは、θ（n）で、高さkの山を構築します。ここで、このヒープからのデキューの前半を考えてください。^K-1 ヒープからのノード。最初の重要な観察結果は、開始ヒープを取り、実際にデキューになってしまうすべてのノードをマークすると、ヒープのサブツリーを形成することです（つまり、dequeuedになるすべてのノードには、dequeuedになる親がいます）。これを見ることができます。なぜなら、これが事実でなければ、ノード自体がデキューであるにもかかわらず、親が（大きい）親がデキューにならなかったノードがあるからです。

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

私たちが答える必要がある最初の質問は、最大2のうちどれだけですか^K-1 ノードはヒープの下位レベルにありませんか？これが2以下であることを示すことができます^K-2 矛盾によって。少なくとも2つあると仮定します^K-2 ヒープの下位レベルの最大ノードの + 1。次に、これらのノードの各親は、レベルk -2の大きなノードでなければなりません。^K-3 レベルk -2の + 1つの大きなノードは、少なくとも2があることを意味します^K-4 レベルK -3などの1つの大きなノード。これらすべてのノードに合計すると、2があることがわかります^K-2 + 2^K-3 + 2^K-4 + ... + 2⁰ + k大きなノード。しかし、この値は厳密に2を超えています^K-1, 、私たちが2つだけで作業しているという事実と矛盾しています^K-1 ここにノード。

さて...私たちは今、せいぜい2があることを知っています^K-2 下層の大きなノード。これは、少なくとも2が必要であることを意味します^K-2 最初のK-2層の大きなノードの。今、私たちは尋ねます - これらのノードのすべてにわたって、そのノードからルートまでの距離は何ですか？さて、2つある場合^K-2 完全なヒープのどこかに配置されたノード、そしてせいぜい2^K-3 それらのそのうちは最初のk -3レベルにある可能性があるため、少なくとも2つあります^K-2 - 2^K-3 = 2^K-3 レベルK -2の重いノード - その結果、実行する必要があるスワップの総数は少なくとも（k -2）2です^K-3. 。 n = 2以降^k-1、k =θ（lg n）、したがって、この値は必要に応じてθ（n lg n）です。

Answer 2

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

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アイテムのみでω（n log（n））が必要なので、下限です（簡単に狭い下限と言うことができます）。

Answer 3

CLRS用語を使用するソリューションは次のとおりです。
私たちは、完全なバイナリツリーであるMaxHeapから始めます n 要素。
完全なバイナリにはあると言えます n/2 葉と n/2 内側のノード。
n/2 の反復 HEAP-SORT 最大のものを削除します n/2 ヒープからの要素。
させて S 最大のセットになります n/2 要素。
せいぜい存在する可能性があります n/4 からの要素 S 追加が必要なので、葉に n/4 内側のノードのそれらの。
させて L これらになります n/4 からの最大の要素 S それは葉の中にあります。
ある場合 n/4 からの要素 S レベル0（葉のレベル）では、少なくともある必要があります n/8 レベル1のそれらの。
させて P これらになります n/8 からの要素 S レベル1です。
n/2 ヒープソートの反復により、その要素が得られる場合があります L ルートへのショートカット、そしてヒープから出るが、からの要素 P ヒープから削除される前に、ルートまでずっと整う必要があります。
少なくともあります (n/8)(lgn-1) 操作。ω（NLGN）の実行時間を提供します。
現在、レベル0のすべての葉がない最大ヒープの場合。
させて k レベル0の葉の数になります。
後 k ヒープソートの反復、私たちは高さの完全なバイナリツリーである最大ヒープが残されています lgn-1.
同じ方法で証拠を継続することができます。
以下が少ない場合 n/4 葉から S.
させて k からの要素の数になります S レベル0の葉にあります。
もしも k <= n/8 少なくともある必要があります n/8 からの要素 S レベル1で。
これは、合計があるからです n/4 レベル1の上の要素。
同じ方法で証明を続けます。
もしも k>n/8 少なくともある必要があります n/16 からの要素 S レベル1です。
同じ方法で証明を続けます。
ヒープソートの実行時間はω（NLGN）であると結論付けています。