ヒープソート

ヒープソートとは？

ソートとは、入力として与えられた数字を小さい順に並び替えることです。ソートの中でも、データ構造のヒープを利用したソートをヒープソートと言います。ヒープについて知りたい方は「アルゴリズム図鑑（2017, 翔泳社）」を参照して下さい。

ヒープソートの実装

pythonで実装を行います。pythonにはheapqという配列をヒープに並び替えることのできるライブラリがあり、これを利用します。ヒープソートを行う関数を以下に示します。

import heapq

def heapsort(array):
    
    n = len(array) # 配列の長さを取得
    sort_array = [] # ソートされたデータを格納するリスト
    
    # ヒープソートを実行
    for _ in range(n):
        heapq.heapify(array) # ヒープに格納
        min_data = array[0] # ヒープは一番上に最小値が来る
        sort_array.append(min_data) # リストに格納
        array.pop(0) # 格納したので削除
    
    return sort_array

この関数に適当に並んだ配列を引数として入力すると、ヒープソートが行われます。

import random

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

まとめ

アルゴリズムの授業の復習と基本情報技術者試験（FE）の対策を兼ねて、ヒープソートの実装を行いました。heapqを使うと簡単に実装できますね。他のソートも実装できるようになりたいです。

全コードは、https://github.com/yuki4031/algorithmにあります。

参考文献

「アルゴリズム図鑑」(2017, 翔泳社)