2

インオーダートラバーサルリストが与えられた場合、バイナリ最小/最大ヒープを作成するための最良の方法は何ですか？

私は次の構成に限定しようとしています：

  1. バイナリヒープで使用される配列はありません。実装はノードベースです。 BinaryNode { value, parent, l_child, r_child }

  2. Max-Heapに固執しましょう。

質問： BubbleDownを含む標準の挿入よりもうまくいくことができますか？

4

1 に答える 1

3

値のコレクションから最大ヒープを構築するための洗練された線形時間アルゴリズムがあります。これは、n個のバブルステップを実行するよりも漸近的に高速です。アイデアは、より小さな最大ヒープのフォレストを構築し、すべての要素が単一の最大ヒープに結合されるまで、それらをペアごとに継続的にマージすることです。正確な分析を使用して、このアルゴリズムが非常に良好な定数係数でO（n）時間で実行されることを示すことができます。多くの標準ライブラリにはこの関数が含まれています。たとえば、C++にはstd::make_heapアルゴリズムがあります。

アルゴリズムのスケッチ、正当性の証明、ランタイム分析など、このアルゴリズムの詳細については、https ：//stackoverflow.com/a/6300047/501557の以前の質問を確認してください。

お役に立てれば！

于 2011-12-26T18:23:19.783 に答える