sorting - 解説 - ヒープソート 計算量




なぜヒープソートは空間の複雑さがO(1)であるのですか? (2)

クールなトリックは、ヒープが完全なバイナリツリーであるため、単純な配列を使用することができ、アイテムi/2親はアイテムi/2ます。

私は、クイックソートとマージソートの両方が、構築された一時サブアレイのためのO(n)補助空間を必要とし、インプレースクイックソートは再帰的スタックフレームのためのO(log n)補助空間を必要とすることを理解する。 しかし、ヒープソートの場合、ノードが実際の要素へのポインタにすぎない場合でも、一時的なヒープを構築するための補助空間の最悪のケースがあるようです。

私はこのexplanation出くわしました:

ヒープはソートされる配列の内部に構築されるため、O(1)の追加スペースしか必要ありません。

しかし、これは、元のアレイがすでにある種のツリーとして実装されていなければならないことを意味すると思いますか? 元の配列が単なるベクトルの場合、ヒープがまだ割り当てられていなければならないというメモリのようです。


配列内のデータはヒープに再配置できます。 このアルゴリズムは実際には驚くほどシンプルですが、ここでは取り上げません。

ヒープ・ソートの場合、データを配置して、ヒープを後ろに最小の要素( std::make_heap )で配置します。 次に、配列の最後の項目(ヒープ内の最小項目)を配列の最初の項目(大きい数字)と入れ替え、その大きな要素をヒープの下にシャッフルして、それが新しい適切な位置にあり、ヒープが配列の最後の要素に残っている最小の要素で、新しいminヒープを返します。 ( std::pop_heap

data:         1 4 7 2 5 8 9 3 6 0

make_heap:   [8 7 9 3 4 5 6 2 1 0] <- this is a min-heap, smallest on right

pop_heap(1): [0 7 9 3 4 5 6 2 1 8] <- swap first and last elements
pop_heap(2): 0 [7 9 3 4 8 6 2 5 1] <- shuffle the 8 down the heap

pop_heap(1): 0 1 [9 3 4 8 6 2 5 7] <- swap first and last elements
pop_heap(2): 0 1 [9 7 4 8 6 3 5 2] <- shuffle the 7 down the heap

etc

したがって、おそらくスワップ・ステップの間を除いて、他の場所に格納する必要はありません。

ビジュアライゼーションのために、標準形式で表示された元のヒープ

make_heap 
           0
     2           1
  3     4     5     6
               8   7 9
pop_heap
           8                           1                           1
     2           1               2           8               2           5 
  3     4     5     6    ->   3     4     5     6    ->   3     4     8     6 
                   7 9                         7 9                         7 9




time-complexity