0

ヒープ ソートは、リンク リストと配列を使用して実装できます。

リンクされたリストまたは配列を使用してそれを行う理想的な方法は何ですか?

配列とリンクされたリストを使用してヒープを構築する時間の複雑さはどれくらいですか?それは両方とも O(nlogn) ですか?

削除の所要時間はどのくらいですか?

4

3 に答える 3

2

配列の場合は O(nlogn) です。インデックス i の要素を簡単にフェッチできるからです。この特性により、各ノードの親と左右の子を簡単に取得できます。削除の時間計算量は O(lgn) です。

リンクされたリストの場合、それは別の話だと思います。「次の」ノードをどのように定義するかによって異なります。私の知る限り、配列を使用するよりも複雑です。

于 2013-01-29T13:45:12.523 に答える
2

バイナリヒープ

ビッグオー記法での時間計算量

        Average        Worst case
Space   O(n)           O(n)
Search  N/A Operation  N/A Operation
Insert  O(log n)       O(log n)
Delete  O(log n)       O(log n)

したがって、連結リスト配列を使用しているかどうかに関係なく、時間の複雑さは同じです。

于 2013-01-29T13:52:25.880 に答える
0

適切な実装を前提として、リンクされたリストまたは配列のいずれを使用しても、時間の複雑さは同じです。

私のブログにはヒープソートの実装がいくつかあります。従来の配列ベースのバージョンについては、ここから開始してから、いくつかのリンク リスト バージョンのリンクをたどってください。

于 2013-01-29T13:48:46.337 に答える