algorithm - O（n）時間でヒープをBSTに変換しますか？

Question

私は答えを知っていると思います、そして最小の複雑さはO（nlogn）です。

しかし、 O（n）の複雑さ のヒープから二分探索木を作成する方法はありますか？

Answer 1

O（n）時間のヒープからBSTを構築するためのアルゴリズムはありません。この理由は、n個の要素が与えられた場合、それらからO（n）時間でヒープを構築できるためです。値のセットのBSTがある場合は、順序どおりにトラバーサルを実行することにより、O（n）時間でそれらを並べ替えることができます。O（n）時間でヒープからBSTを構築できる場合は、次の方法でO（n）ソートアルゴリズムを使用できます。

1. O（n）時間でヒープを構築し、
2. O（n）時間でヒープをBSTに変換し、
3. ソートされたシーケンスを取得するためにO（n）時間でBSTを歩きます。

したがって、O（n）時間（またはo（n log n）時間、oはlittle-o表記）でヒープをBSTに変換することはできません。

ただし、BSTから最大値を繰り返しデキューし、ツリーの右端のノードとして挿入することにより、O（n log n）時間のヒープからBSTを構築することができます。（高速アクセスを行うには、そこにポインタを格納する必要があります。ルートに繰り返し挿入するだけで、O（n ²）時間がかかります。）

お役に立てれば！