配列を使用したバイナリヒープの形成ショートカット

Question

配列を昇順に並べると、バイナリヒープになります。この利点の欠点はありますか？はいの場合は、その理由は何ですか？

Answer 1

「配列を昇順に並べ替えると、バイナリヒープになります。これは正しいです。 これは、配列を昇順で並べ替えるアルゴリズムによって異なります。最適な並べ替えアルゴリズムは、複雑さO(NLogN)で実行します。

バイナリヒープを作成するアルゴリズムBuild_Heapは、O(N)の複雑さを持ちますが、

Counting Sortなどの非比較ソート方法を使用するまで、バイナリヒープを作成する複雑さは少なくともとatmost O(N^2)になります。

バイナリヒープを作成する従来の方法が好都合です。

伝統的なBuild_Heapインプレースバイナリヒープを作成するが、Counting SortはO(N)時間がかかりますが、それは余分なスペースO(N)が必要になりますが。