17/04/23

pythonでヒープソート


今回はソートアルゴリズムの、ヒープソートついて解説、pythonで実装していきます。
ヒープソートは配列の中で二本木(ヒープ)を構築しながらソートを行っていきます。

ヒープソートについて

2分木(ヒープ)というデータ構造で半順序木を使って行うアルゴリズムです。
2分木というのは枝が2つに分かれているような様子のデータ構造のことをいいます。
一つ下にある2つの要素を子、一つ上にある要素を親、最上にある要素を根(ルート)といいます。

 

親と子に大小関係があり、子の右側と子の左側にも大小関係があるものを順序木と言い、
親と子だけに大小関係があるものを半順序木といいます。

手順

  • 半順序木を作成する。
  • ルートと子の末端つまりli[1]とli[N]を交換する
  • Nがソート済みになったので、N -= 1
    *N > 0になるまで繰り返す

 

配列はN個のデータを持ち、インデックスは1からNとします。
計算しやすくするために配列の0に空を入れ、
配列[,9,8,6,1,3,2,5]を2分木にすると以下のようになります。
heap_sort1

 

ここで規則性として
親のインデックス(n)を2倍(2n)すると左下の子になり、2倍+1(2n+1)すると右下の子になります。
また配列の末端が二分木の末端(最も右下)になります

 

配列[6,1,5,8,3,2,9]を上記の手順でソートするのをgifで視覚化すると以下のようになります
heap_sort

ソースコード

import math;

def heap_sort(li):
    #計算が行いやすいようにnum[0]に0を代入する
    length = len(li);
    li.insert(0,0);

    # 末端
    end = length;
    # 親となる数を取得
    parent = math.floor(length / 2);

    # 半順序木を作成
    while parent > 0:
        li = down_heap(li, end, parent);
        parent -= 1;

    while end > 0:
        # このとき半順序木のルートは最大値である。
        # 半順序木のルートと末尾の要素を交換する。
        # 末尾の要素は最大、つまりソート済みなので除外する
        #li[0]は計算しやすくするために空が入っているので無視する
        li = swap(li, 1, end);
        end -= 1;

        # 半順序木を再構築する
        li = down_heap(li, end, 1);

    # li[0]の0を除く
    return li[1:];

#半順序木(ヒープ)を作成
def down_heap (li,end,parent):
    # 子[n]の値
    i = parent * 2;

    while i <= end:
        # 子[n]と子[n+1]を比較して大きい方のindexを管理する
        if i < end and li[i] < li[i + 1]:
            i += 1;

        # 親のほが大きいもしくは同等なら既に親と子に大小関係があるので処理を抜ける
        if li[parent] >= li[i]:
            break;

        swap(li, parent, i);

        # 親と子を入れ替えたので、次に子と孫を比較し、
        # 次に入れ替えた子と孫を比較し、半順序木を再構築する。
        parent = i;
        i = parent * 2;

    return li;

# 要素の入れ替え
def swap(li,i,j):
    temp = li[i];
    li[i] = li[j];
    li[j] = temp;

    return li;


heap_sort([9,8,2,10,2])
# [2, 2, 8, 9, 10]

以上です。

 

参考サイト
C言語講座

 

スポンサーリンク

メールアドレスが公開されることはありません。

youya66

だらけとびびり、それとちょっぴりのてきとーさ。

コアラになってだらだらしながら愛されたい。