Python初心者がヒープソートを整理する

これは備忘録です

基本情報を取って以降まったく触っていなかったのでヒープソートってどんなだっけ？って思い知識の整理をしながらメモをしようと思った。
(6/23　同僚にミスを指摘されたので修正。見直し大事)

パクる 引用させていただく

なんにしてもアルゴリズムを一から作ることもできなくはないが正直しんどいので[参考：A]のサイトから引用し、自分で分解しながら整理しようと思う。

そもそもヒープソートって？

大体のルールを画像でメモしました

なんでこんなにややこしいことを考えたかは知らないけど配列の操作関係上、上下の操作がしやすいらしい。木構造はOracleDBとかでも使っているらしいし(うるおぼえ)、データの検索効率がいいらしい。

三つの求め方に関しては覚えるべき点だと思うので特筆して書きました。

本体

ヒープソート本体の関数。ここに引数として配列を入れるとソートされる

heap_sort.py

def heap_sort(array):
    i = 0
    n = len(array)
    # ヒープを構成
    while(i < n):
        upheap(array, i)
        i += 1
    while(i > 1):# n～0まで
        # ヒープから最大値を取り出し
        i -= 1
        array[0] , array[i] = array[i] , array[0]

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

配列を受け取ったら長さとインデックスを定義（いつもの）。

そしてupheaoにインデックスを渡しながら0～ラストまでループを回します。

多分自分が書くとfor i in range(len(array))とか書きそう。nとかここでしか使わないし。読みづらさ？ｼﾗﾅｲ

そして、downheepのループ。正直この記事を書こうと思ったきっかけ。わかりづらいんじゃ

ちなみに、
array[0] , array[i] = array[i] , array[0]
はスワップです。pythonではこう書けるらしいからやってみた。1行で済むのは正義。

upheapって？

upheapは引数として配列とインデックスを受け動きます。
本体からはarrayとiを受け取ります。
ちなみにwhile nはwhile n!=0のことです。0じゃなきゃtrueってこと。

upheap.py

def upheap(array, n):
    while n:
        parent = int((n - 1) / 2)
        # 親＞子　の値を取るようにする
        if array[parent] < array[n]:
            array[n] , array[parent] = array[parent] , array[n]
            n = parent
        else:
            break

これは、小さい数を子に渡していくという作業です。ヒープは基本的に「親が小さい、子が大きい」という法則なのでこれを一度やらないと大きい数字を子に渡せなくなります。
なので、一度上(親側)に大きい数字を渡していき子に大きい数字を渡す準備をします。

before [1, 2, 3, 4, 5, 3, 2, 1, 4, 3, 4, 5, 0]
upheap [5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0]

こんな感じでソートされます

downheepって？

downheapは引数として配列とインデックスを受け動きます。
本体からはarrayとi-1を受け取ります。

downheap.py

# ルート[0]をヒープ(0～n)の最適な位置へ移動
def downheap(array, n):
    if n==0: return
    parent = 0
    while True:
        child = 2 * parent + 1 # array[n]の子要素
        # 要素外へ出るとbrake
        if child > n:
            break
        # 隣の子がいてかつ　左　＜　右　なら　右の子を見る
        if (child < n) and array[child] < array[child + 1]:
            child += 1
        # 親が子より小さい場合スワップ
        if array[parent] < array[child]: 
            array[child] , array[parent] = array[parent] , array[child]

            parent = child; # 交換後のインデックスを保持
        else:
            break

結構注釈入れたけどそれでも分かりづらいかな？
前提条件として、この関数入る前に
array[0] , array[i] = array[i] , array[0]
をしています。(iはフォーカスしてる部分)
これをやることでソート前の最下位の子に一番大きい数字を渡し、次に渡すための一番大きな数を最上位の親にもってくる。ということができます

before[1,2,3,4,5,3,2,1,4,3,4,5,0]
upheap[5, 4, 5, 4, 4, 3, 2, 1, 1, 3, 3, 2, 0]
[5, 4, 3, 4, 4, 2, 2, 1, 1, 3, 3, 0, 5]
[4, 4, 3, 1, 4, 2, 2, 0, 1, 3, 3, 5, 5]
[4, 4, 3, 1, 3, 2, 2, 0, 1, 3, 4, 5, 5]
[4, 3, 3, 1, 3, 2, 2, 0, 1, 4, 4, 5, 5]
[3, 3, 3, 1, 1, 2, 2, 0, 4, 4, 4, 5, 5]
[3, 1, 3, 0, 1, 2, 2, 3, 4, 4, 4, 5, 5]
[3, 1, 2, 0, 1, 2, 3, 3, 4, 4, 4, 5, 5]
[2, 1, 2, 0, 1, 3, 3, 3, 4, 4, 4, 5, 5]
[2, 1, 1, 0, 2, 3, 3, 3, 4, 4, 4, 5, 5]
[1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]
[1, 0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]
[0, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5]

フォーカスインデックスが上位に行くにつれ、下位のデータにソートされた数字が溜まっていくのがわかるでしょうか。
こうすることできれいなソートができます。

最後に

今回、記事を書きながらアルゴリズムの整理をしていたが、勘違いしていたことも結構あって自分の説明ができる限り正しいものになるようにトレースして確認を繰り返した。
このような形は勉強になるので自己満足で続けれたらと思う。

参考

[参考：A]https://webbibouroku.com/Blog/Article/py-heapsort
丸パク引用させていただきました。本家のほうが正確な説明をしていると思うので、下手にかみ砕かれたものが嫌いな方は本家でご理解ください。

[参考：B]http://www.it-shikaku.jp/top30.php?hidari=02-02-02.php&migi=km02-02.php
後から見つけたまとめサイト。疑似言語のっているのがｽｺﾞｸｲｲ