【基本情報技術者試験】ヒープソートをPythonで実装

今回はヒープソートをPythonで実装します。

基本交換法（バブルソート）
基本選択法（選択ソート）
基本挿入法（挿入ソート）
シェルソート
クイックソート
マージソート
ヒープソート←今回の対象

ヒープソートとは？

ヒープソートとは二分ヒープ木を用いてソートしていくアルゴリズムです。二分ヒープ木は親ノードは子ノード以上の値となるというのを利用してソートしています。
例えば8, 3, 1, 2, 7, 5, 6, 4という数列があったときに下記のように更新していきます。

① 二分ヒープ木の作成

上記の数列のツリー状に表すと下記のようになります。

親ノード>=子ノードとなるように入替を行うと下記の赤字部分が入れ替えられます。

同様にして入替を続けていきます。そうすると最終的に8, 7, 6, 4, 3, 1, 5, 2の並びとなります。

② 次に先頭と末尾の数値を入れ替えて、末尾の数値を固定することで末尾に最大の数値がくるようにソートしていきます。

8と2を入れ替えて、8を固定する。その後８以外の数値で二分ヒープ木を作成する。

同様にして、先頭と末尾の数値の入替と二分ヒープ木の作成を繰り返します。

そうすると最終的に1, 2, 3, 4, 5, 6, 7, 8の並びとなりソートできます。

これをPythonで実装すると下記のようになります。

# array[n]をヒープ構成部(0～n-1)の適切な位置へ移動
def upheap(array, n):
  while n > 0:
    parent = (n - 1) // 2
    # 親より大きな値の場合、親子の値を交換
    if array[n] > array[parent]:
      array[n], array[parent] = array[parent], array[n]
      n = parent
    else:
      break

# ルート[0]をヒープ(0～n)の適切な位置へ移動
def downheap(array, n):
  if n == 0:
    return
  parent = 0
  while True:
    child = 2 * parent + 1 # array[n]の子要素
    if child > n:
      break
    if (child < n) and array[child] < array[child + 1]: # 子要素の大きい方をスワップ対象とする
      child += 1
    if array[parent] < array[child]: # 子要素より小さい場合スワップ
      array[child], array[parent] = array[parent], array[child]
      parent = child; # 交換後のインデックスを保持
    else:
      break

# ヒープソート
def heapsort(array):
  i = 0

  while(i < len(array)):
    # ヒープを構成
    upheap(array, i)
    print(array)
    i += 1

  print("downheap")
  while(i > 1):
    # ヒープから最大値を取り出し
    i -= 1
    array[0], array[i] = array[i], array[0]

    # ヒープの再構成
    downheap(array, i - 1)
    print(array)

listNum = [8, 3, 1, 2, 7, 5, 6, 4]

listNum

[8, 3, 1, 2, 7, 5, 6, 4]

heapsort(listNum)

[1, 2, 3, 4, 5, 6, 7, 8]

以上でヒープソートの実装は終わりです。