ヒーププロパティ(Cormen)を使用してソート順にツリーを表示する

私はアルゴリズム理論(Cormenから)に爽快です。
バイナリ試行の章には、次のような質問があります。

n-nodeのキーを出力するためにmin-heapプロパティを使用することはできますか
  O(n)時間でソートされた順序でツリー?方法を示したり、理由を説明してください。

私はそれが可能だと思った。
最小ヒープでは、ノードの要素は両方の子要素よりも小さくなります。
したがって、ヒープのルートは、常にn個の要素のうちの小さい方の要素であり、ルートの左の子は、左のサブツリーのすべての要素よりも小さく、ルートの右の子は、右サブツリーなど

したがって、ルートを抜き出して印刷してから、そのルートの子を小さなものに更新すると、最小ヒーププロパティが保持され、ソートされた順序で印刷されます。
(私はアレイベースではない最小のヒープを考えています)。

これは、ルートを更新するためにO(n)時間後に実行できます.2つの子を比較し、ルートのポインタを更新して2のうちの小さい方にします。

しかし、ここで解決策を確認しました:
Cormen補足ソリューション

そして1)それは最大ヒープについて話している2)それはO(n)の時間には行えないと言っている:

ヒープでは、ノードのキーは両方の子キーです。バイナリ
  検索ツリーでは、ノードのキーは左の子のキーですが、その右
  子供の鍵。ヒーププロパティは、バイナリシースツリーとは異なり
  プロパティは、ソートされた順序でノードを表示するのに役立たない
  印刷する要素がノードのどのサブツリーに含まれているかはわかりません
  そのノードの前に。ヒープでは、ノードより小さい最大の要素
  どちらのサブツリーにもあり得ます。ヒーププロパティが
  O(n)時間内にソートされた順序でキーを印刷するために使用される場合、私たちは
  ソートのためのO(n)時間アルゴリズム   定刻。しかし、われわれは(第8章)
  (ng n)時間。

私の見解では、最大ヒープを使用すると、O(n)で印刷することはできません。
しかし、私が説明した推論のためにmin-heapプロパティを使用してそれを行うことはできませんか?
また、ソリューションがmin-heapを無視する理由もあります。それはタイプミスかエラーですか?

私はここで何かを誤解していますか?

ベストアンサー

まず、ディスカッションの中の最小ヒープの省略はおそらくタイプミスではなく、最小ヒープまたは最大ヒープについて話しているかどうかは関係ありません(コンパレータはちょうど逆になります)。

ルートを抽出して2人の子供のうち小さい方に置き換えるだけで問題になるのは、左側の子が右側のサブツリー(およびその逆)のすべてのノードよりも小さくなることが保証されていないことです。次のヒープを考えてみましょう

        1
      /
      4   6
     /   /
    5  8 9  7

1 を印刷した後、 1
を抽出して最後の行の最後の要素と置き換えると言います。この場合 7
。ヒープを正しい状態に戻す必要がある場合は、スイッチを入れます

take away root and last node to root
        7
      /
      4   6
     /   /
    5  8 9

swap
        4
      /
      7   6
     /   /
    5  8 9

swap
        4
      /
      5   6
     /   /
    7  8 9

そのスワッピングはすべてあなたが log n 時間を費やします。

代わりにルートノードを 4
に置き換えた場合は、ルートノードを抽出する線形コス​​トにコストを追加するために、左分岐を実行する必要があります。もしヒープがこのように見えるなら

        1
      /
      4   9
     /   /
    5  6 11 15
   /
  8  7

ソリューションを形成するために私が見たページ

1) Wikipedia: binary heap

2) Wolfram MathWorld:heap
ここでのヒープは、それが線形操作ではない理由を理解するのに特に役立ちます。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です