最小/最大バイナリヒープを構築する

Question

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

私は、次の構文を制限するようにしようとしている：バイナリヒープで使用する

1. ませ配列。実装はノードベースです。 BinaryNode { value, parent, l_child, r_child }

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

質問：我々はBubbleDownを伴う標準の挿入よりも良い行うことができます。

Answer 1

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

・ホープ、このことができます：アルゴリズムのスケッチ、正しさの証明、およびランタイム分析など、このアルゴリズムの詳細については、

、これ以前の質問をチェックしてください！