ヒープソートとは

IT用語

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

はじめに

情報処理試験問題でよく登場する整列アルゴリズムの問題。

基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」、そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。

本記事では、未整列データを木構造にしてソートしていく「ヒープソート」について図解を利用してわかりやすく解説しています。

スポンサーリンク

ヒープソートとは

ヒープソートとは未整列のデータを「順序木」といわれる木構造の構成にして、そこから最大値または最小値を取り出して整列、これを繰り返すことで全体を整列させる手法です。

  1. 未整列データを木構造にする。
  2. 木構造の根(ルート)が最大値または最小値になるように並び替えを行う。
  3. 並び替えが完了した木構造の根(ルート)の値を整列済みデータとする。
  4. 1~3を繰り返して、全て整列済みデータになったら終了。

 

それでは具体的に図解でヒープソートの流れを説明していきます。今回は木構造の根(ルート)が最大値になるパターンで説明します。

暗記ポイント

ヒープソートとは、木構造を利用して並び替えを行う整列アルゴリズム

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

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

ヒープソート手順1

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

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

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

 

ヒープソート手順2-1

次に上のグループを比較

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

ヒープソート手順2-2

次に隣のグループを比較

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

ヒープソート手順2-3

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

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

ヒープソート手順2-4

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

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

ヒープソート手順2-5

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

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

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

ヒープソート手順3

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

スポンサーリンク

一番下のグループを比較

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

ヒープソート手順4-1

隣のグループを比較

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

ヒープソート手順4-2

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

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

ヒープソート手順4-3

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

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

ヒープソート手順4-4

【手順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

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

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

ヒープソート手順5-3

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

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

ヒープソート手順5-4

ヒープソート手順5-5

スポンサーリンク

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

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

ヒープソート手順5-6

ヒープソート手順5-7

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

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

ヒープソート手順5-8

ヒープソート手順5-9

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

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

ヒープソート手順5-10

 

 

[基本整列アルゴリズム]

[高速整列アルゴリズム]

Copyright© ITを分かりやすく解説 , 2020 All Rights Reserved Powered by AFFINGER5.