[Python] ヒープソートの実装方法とアルゴリズム

ヒープソートの実装方法とアルゴリズム

Pythonでヒープソートを実装してみます。Python3.6を使います。

常に最大値(最小値)を取り出すことができるデータ構造があれば、それを使ってソートアルゴリズムが実装できるという考えのもと、考案されたのがヒープソートです。ソートは2分ヒープと呼ばれる木構造を使います。

2分ヒープは2分木で、子ノードが常に親ノードより小さいことが保障される木構造です。したがってルートノードが常に最大値となります。

ヒープソートの手順としては、まず与えられたソート対象のデータで2分ヒープを構成します。そして最大値の取り出し/2分ヒープの再構成をくりかえしながらデータを並べ替えます。ヒープへの追加、ルートノードの削除がキーとなる操作です。

ヒープソートは時間計算量 O(n log n) でバブルソートや選択ソートより圧倒的に速くなります。ただしデータの出現順序によっては2分ヒープが片側に偏ってしまい、最悪の場合 O(n²) となってしまいます。

ヒープへの追加とUpHeap

ヒープの整合性を保った状態で要素を追加するには UpHeap と呼ばれる方法を用います。ヒープ末尾(最下層)に要素を追加し、これを親要素と比較しながら最適な位置まで移動させます。

ルート要素の削除とDownHeap

ヒープソートではヒープを配列で管理するので、実際には削除するのではなく、末尾の要素をルートと入れ替えます。これだけでは整合性が保てないので、ルート要素を正しい位置まで移動させる必要があります。この手順を DownHeap と呼びます。

末端要素を繰り上げる UpHeap と丁度対照的な操作になります。ルート要素を子要素と比較/交換をくりかえします。

サンプルコード

# ヒープソート
def heap_sort(array):
    i = 0
    n = len(array)

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

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

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

# array[n]をヒープ構成部(0～n-1)の最適な位置へ移動
def upheap(array, n):
    while n != 0:
        parent = int((n - 1) / 2)
        if array[n] > array[parent]:
            # 親より大きな値の場合親子の値を交換
            tmp = array[n]
            array[n] = array[parent]
            array[parent] = tmp
            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]: # 子要素より小さい場合スワップ
            tmp = array[child]
            array[child] = array[parent]
            array[parent] = tmp
            parent = child; # 交換後のインデックスを保持
        else:
            break

# デバッグ
if __name__ == "__main__":
    array = [1,2,3,4,5,3,2,1,4,3,4,5,0]
    print("before", array)
    heap_sort(array)
    print("after ", array)

ヒープソートの流れ

ヒープソートは内部ソートとして実装できます。したがって外部領域を使わず配列内でソートを行います。まず、配列の先頭(a[0])のみで構成されるヒープを考えます。これの末尾に要素(a[1])を追加し、整合性を保つ位置まで移動(UpHeap)します。これをくりかえしていけば、配列全体でヒープを高背することができます。

ヒープの構成が完了すると、ルート要素(a[0])が最大値になっています。これをヒープ構成部分末尾(a[n])と入れ替えます。a[0..n-1]でヒープを再構成するために a[0] を整合性を保つ位置まで移動(DownHeap)します。これをくりかえしていくと、ヒープ構成部分が小さくなり、配列の末尾から順に大きな値で埋まっていく次第です。

参考URL

• ヒープソート – Algoful
• ヒープソート – Wikipedia
• 二分ヒープ – Wikipedia