[Python] ヒープソート

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

ヒープソート

ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである^[2]（ヒープ領域とは無関係であることに注意する）。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

データ構造としての2分ヒープは下記で扱いました。

ヒープソートのイメージは下記の画像が大変分かりやすいです。

「max-heap の特性を満たすように配列を操作しルートを取る」という操作を繰り返すことで、最大値から順に値を取り出すことができます。

コードは下記を参照しています。

HeapSort

import random

def max_heapify(array, n, i):
  """
  array : 対象とする配列
  n : heapifyの対象とする最後のインデックス
  i : subtree の root のインデックス
  """
  # ルート array[i]
  # とりあえずルートが最大
  largest = i
  left  = 2 * i + 1
  right = 2*  i + 2
  
  # 左側の子がルートより大きい場合
  if left < n and array[i] < array[left]:
    largest = left
  
  # 右側の子がルートよりも左側よりも大きい場合
  if right < n and array[largest] < array[right]:
    largest = right
  
  # ルート以外がルートより大きい場合は入れ替え
  if largest != i:
    array[i], array[largest] = array[largest], array[i]
    
    # 入れ替えのあったsubtreeでmax-heapを満たすようにheapifyを行う
    max_heapify(array, n, largest)

def heap_sort(array):
  n = len(array)

  # max-heapを作る
  for i in range(n//2, -1, -1):
    max_heapify(array, n, i)
  
  # 配列の最初の最大値と配列の最後と交換する。
  # 配列の最後を除いた配列で、再びmax-heapを作る。
  for i in range(n-1, 0, -1):
    array[i], array[0] = array[0], array[i]
    max_heapify(array, i, 0)


if __name__ == '__main__':

  random.seed(1)
  array = [random.randrange(100) for i in range(10)]
  print('未ソート', array)
  # 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60]
  heap_sort(array)
  print('ソート済み', array) 
  # ソート済み [8, 15, 17, 32, 57, 60, 63, 72, 97, 97]

想定通りの結果になりました。