ヒープソートとは

プログラム

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

はじめに

基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。

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

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

ヒープソートとは

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

ヒープとは「半順序木」ともいわれ、「親 ≧ 子」もしくは「親 ≦ 子」という関係にある2分木のことです。

ヒープソートの流れ

  • 未整列の配列からヒープの性質を持つ木構造を作成する
  • 木構造の作成が完了したら、根（ルート）の値を整列済みとする
  • 根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る
  • すべてのデータが整列済みになるまで、手順2～3を繰り返す

暗記ポイント

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

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

スポンサーリンク

【手順1】未整列の配列からヒープの性質を持つ木構造を作成する

未整列データをヒープの性質を持つ木構造を作成します（「親 ≧ 子」となるように並び替える）

ヒープソート手順1-1

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

  1. 一番下の葉である子「2」と親「7」が「親 ≧ 子」になっているか確認する
  2. ここでは親「7」の方が大きいのでそのままとする

 

ヒープソート手順1-2

次に上のグループを比較

  1. 次に一つ上のグループである親「3」と子「7」「1」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「7」が一番大きい数値なので、「3」と「7」を入れ替える

ヒープソート手順1-3

  1. 「3」が移動してきたグループが「親 ≧ 子」になっているか確認する
  2. 親「3」、子「2」と「親 ≧ 子」になっているのそのままとする

次に隣のグループを比較

  1. 次に隣のグループである親「5」と子「8」「6」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「8」が一番大きい数値なので、「5」と「8」を入れ替える

ヒープソート手順1-4

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

  1. 次に一番上のグループである親「4」と子「7」「8」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「8」が一番大きい数値なので、「4」と「8」を入れ替える

ヒープソート手順1-5

  1. 「4」が移動してきた右下のグループが「親 ≧ 子」になっているか確認する
  2. 3つの中では「6」が一番大きい数値なので、「4」と「6」を入れ替える

ヒープソート手順1-6

ヒープの性質を持つ木構造の作成は完了です。

【手順2】木構造の作成が完了したら、根（ルート）の値を整列済みとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「8」を追加します。

ヒープソート手順2

【手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

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

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

ヒープソート手順3-1

一番上のグループを比較

「2」を一番下から一番上の根（ルート）に持ってきたため、「親 ≧ 子」になっている保証がありません。そのため、一番上のグループを比較します。

（根に移動してきた「2」以外は「親 ≧ 子」になっているので「2」の部分を整列していく）

  1. 一番上のグループである親「2」と子「7」「6」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「7」が一番大きい数値なので、「7」と「2」を入れ替える

左下のグループを比較

「2」が移動してきた左下のグループは「親 ≧ 子」になっている保証がないため、左下のグループを比較します。

  1. 左下のグループである親「2」と子「3」「1」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「3」が一番大きい数値なので、「2」と「3」を入れ替える

ヒープソート手順3-3

ヒープの性質を持つ木構造の作成は完了です。

【手順4】すべてのデータが整列済みになるまで、手順2～3を繰り返す

【4-1手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「7」を追加します。

ヒープソート4-1手順2

【4-1手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

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

この時、一番下の「4」を一番上に持っていきます。

ヒープソート4-1手順3-1

  1. 一番上のグループである親「4」と子「3」「6」が「親 ≧ 子」になっているか確認する
  2. 3つの中では「6」が一番大きい数値なので、「4」と「6」を入れ替える
  3. 「4」が移動してきた右下のグループは「親 ≧ 子」になっている保証がないため「親 ≧ 子」になっているか確認する
  4. 親「4」より子「5」の方が大きい数値なので、「4」と「5」を入れ替える

ヒープソート4-1手順3-2

【4-2手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「6」を追加します。

ヒープソート4-2手順2

【4-2手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

  1. 整列済みデータとなった「6」を除いた未整列データで再び木構成を作る（一番下の「4」を一番上に移動する）
  2. 一番上のグループである親「4」と子「3」「5」が「親 ≧ 子」になっているか確認する
  3. 3つの中では「5」が一番大きい数値なので、「4」と「5」を入れ替える

ヒープソート4-2手順3

【4-3手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「5」を追加します。

ヒープソート4-3手順2

【4-3手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

  1. 整列済みデータとなった「5」を除いた未整列データで再び木構成を作る（一番下の「1」を一番上に持ってくる）
  2. 一番上のグループである親「1」と子「3」「4」が「親 ≧ 子」になっているか確認する
  3. 3つの中では「4」が一番大きい数値なので、「1」と「4」を入れ替える

ヒープソート4-3手順3

【4-4手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「4」を追加します。

ヒープソート4-4手順2

【4-4手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

  1. 整列済みデータとなった「4」を除いた未整列データで再び木構成を作る（一番下の「2」を一番上に持ってくる）
  2. 一番上のグループである親「2」と子「3」「1」が「親 ≧ 子」になっているか確認する
  3. 3つの中では「3」が一番大きい数値なので、「2」と「3」を入れ替える

ヒープソート4-4手順3

【4-5手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「3」を追加します。

ヒープソート4-5_2

【4-5手順3】根（ルート）の値を除いて、再度ヒープの性質を持つ木構造を作る

  1. 整列済みデータとなった「3」を除いた未整列データで再び木構成を作る（一番下の「1」を一番上に持ってくる）
  2. 一番上のグループである親「1」と子「2」が「親 ≧ 子」になっているか確認する
  3. 親「1」より子「2」の方が大きいので、「1」と「2」を入れ替える

ヒープソート4-5_3

【4-6手順2】木構造の作成が完了したら、根（ルート）の値を整列済みデータとする

木構造の作成が完了した（一番上の根（ルート）が最大値になった）ので、整列済みデータに最大値の「2」を追加します。

そして、最後に残った「1」を整列済みデータに追加すれば完了です。

ヒープソート4-6_2

 

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

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