Pythonで学ぶアルゴリズム 第19弾：並べ替え（ヒープソート）

#Pythonで学ぶアルゴリズム< ヒープソート >

はじめに

基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第19弾としてヒープソートを扱う．

ヒープソート

前回扱ったスタックとキューに対して，ヒープソートはヒープと呼ばれる木構造によりデータを扱う．
ヒープは子ノード間での制約はないが親ノードと子ノードでの大小関係の制約がある．場合により，
（親$\le$子），(親$\ge$子)のようになる．今回は小さいものからデータを扱うために制約は（親$\le$子）とする．そのイメージ図を次に示す．

1親ノードに対して2子ノードの構造をもつヒープを特に二分ヒープという．
これを今まで扱ってきたようにリストのデータをこのヒープ構造に落としこむ．このときヒープ構造に落としこむということは木の上から順に小さな値となっていることが分かる．すなわち，一番上の親ノードを取り出すと，そのときの最小値が得られる．その様子を次に示す．

図にあるように，二分木が崩れてしまう．そのときには一時的に末尾が一番上に移動し，二分木構造を補う．しかしながら，必然的に親ノードと子ノードの制約条件を満たさないことが多くなる．ヒープソートでは常にヒープ構造を保とうと，再び制約条件に従いヒープ構造を整える．その様子を次に示す．

このヒープ構造修正後も次に示す．

上図より，再びヒープが構成され，そのときの最小値が一番上の親ノードにあることが分かる．
この操作を繰り返すことで，昇順に並べ替える．

ここで，リストとヒープの対応付けを次に示す．

実装

Pythonの標準ライブラリを用いたコードとそのときの出力を以下に示す．

コード

heap_sort.py

"""
2021/01/16
@Yuya Shimizu

ヒープソート
"""
import heapq    #ヒープを扱うPython標準ライブラリ

def heap_sort(data):
    DATA_FOR_HEAP = data.copy()     #ヒープを作るためのデータを格納
    heapq.heapify(DATA_FOR_HEAP)    #ヒープ生成（最小順に並んだ木構造）
    return [heapq.heappop(DATA_FOR_HEAP) for _ in range(len(data))] #heappop関数で順に取り出す

if __name__ == '__main__':
    DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]

    sorted_data = heap_sort(DATA)

    print(f"{DATA} → {sorted_data}")

出力

[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]

計算量

スタックとキューではオーダー記法で表すと計算量は$O(n^2)$であったが，ヒープソートではその計算量が$O(log(n))$となる．$n$の数（データ数）が大きくなった時でもそこまで計算量が大きくならないことが分かる．

感想

標準ライブラリを用いず，再帰などを駆使してアルゴリズムを記述方法も紹介されていたが，ここでは省く．アルゴリズムについては理解できたし，Pythonに標準ライブラリがあるならそれを使えばよいのではないかと思う．アルゴリズム自体は理解しているため，必要となれば，そのときに改めてアルゴリズムに立ち返ればよいと考える．残りはマージソートとクイックソートの2つで並べ替えアルゴリズムの終わりが見えてきた．次回も楽しみである．

参考文献

Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社