ヒープソートとは | 分かりやすく図解で解説

【手順1】未整列データを木構造にする

未整列データを木構造にします。

【手順2】下から順番に入れ替えを行い、木構造の根（ルート）が最大値になるようにする

まずは一番下の葉から比較

1. 一番下の葉である"2"と親の"7"を比較します
2. ここでは"7"の方が大きいのでそのままとします。

 

次に上のグループを比較

1. 次に一つ上のグループである"3"と"7"と"1"を比較します。
2. 3つの中では"7"が一番大きい数値なので、"7"と"3"を入れ替えていきます。

次に隣のグループを比較

1. 次に隣のグループである"5"と"8"と"6"を比較します。
2. 3つの中では"8"が一番大きい数値なので、"8"と"5"を入れ替えていきます。

次に一番上のグループを比較

1. 次に一番上のグループである"4"と"7"と"8"を比較します。
2. 3つの中では"8"が一番大きい数値なので、"8"と"4"を入れ替えていきます。

根（ルート）が最大値になったので整列済みデータへ追加

1. これで一番上の根（ルート）が最大値になりました。
2. 整列済みデータに最大値の"8"を追加します。

【手順3】再び未整列データを木構造にする

整列済みデータとなった"8"を除いた未整列データで再び木構成を作ります。

この時、一番下の"2"を一番上に持っていきます。

【手順4】手順2と同様に下から順番に入れ替えを行い、木構造の根（ルート）が最大値になるようにする

スポンサーリンク

一番下のグループを比較

1. 一番下のグループである"7"と"3"と"1"を比較します。
2. ここでは"7"が一番大きいので、そのままとします。

隣のグループを比較

1. 次に隣のグループである"4"と"5"と"6"を比較します。
2. 3つの中では"6"が一番大きい数値なので、"6"と"4"を入れ替えていきます。

次に一番上のグループを比較

1. 次に一番上のグループである"7"と"2"と"6"を比較します。
2. 3つの中では"7"が一番大きい数値なので、"7"と"2"を入れ替えていきます。

根（ルート）が最大値になったので整列済みデータへ追加

1. これで一番上の根（ルート）が最大値になりました。
2. 整列済みデータに最大値の"7"を追加します。

【手順5】手順3～手順4を繰り返していく

再び木構成を作り、"6"を整列済みデータへ格納

1. 整列済みデータとなった"8"と"7"を除いた未整列データで再び木構成を作る（一番下の"4"を一番上に持っていく）
2. 左下のグループ（"3","2","1"）で比較。"3”が一番大きいので、"3”と"2"を入れ替える
3. 右下のグループ（"5","6"）で比較。"6"が一番大きいので、そのままとする
4. 一番上のグループ（"3","4","6"）で比較。"6"が一番大きいので、"6"と"4"を入れ替える
5. 整列済みデータに最大値の"6"を追加します。

 

再び木構成を作り、"5"を整列済みデータへ格納

1. 未整列データで再び木構造を作る（一番下の"5"を一番上に持っていく）
2. 左下のグループ（"2","3","1"）で比較。"3"が一番大きいのでそのままとする
3. 上のグループ（"3","5","4"）で比較。"5"が一番大きいのでそのままとする
4. 整列済みデータに最大値の"5"を追加します。

再び木構成を作り、"4"を整列済みデータへ格納

1. 未整列データで再び木構成を作る（一番下の"1"を一番上に持っていく）
2. 左下のグループ（"2","3"）で比較。"3”が一番大きいので、そのままとする
3. 一番上のグループ（"3","1","4"）で比較。"4"が一番大きいので、"4"と"1"を入れ替える
4. 整列済みデータに最大値の"4"を追加します。

スポンサーリンク

再び木構成を作り、"3"を整列済みデータへ格納

1. 未整列データで再び木構成を作る（一番下の"2"を一番上に持っていく）
2. グループ（"3","2","1"）で比較。"3"が一番大きいので、"3"と"2"を入れ替える
3. 整列済みデータに最大値の"3"を追加します。

再び木構成を作り、"2"を整列済みデータへ格納

1. 未整列データで再び木構成を作る（一番下の"1"を一番上に持っていく）
2. グループ（"2","1"）で比較。"2"が一番大きいので、"2"と"1"を入れ替える
3. 整列済みデータに最大値の"2"を追加します。

最後の"1"を整列済みデータへ格納

最後に残った"1"も整列済みデータに追加します。