アルゴリズムクイックリファレンス第二版 レビュー 特にヒープソートについて

元々は、要約ノートはこういう、つまりコードをpythonに直して、重要そうな部分を抜き出し書きにするつもりだった。
まあそういうことをやろうとしていた人間が図々しいとは思うけど、この本を買おうとしている人は、立ち読みでヒープソートの所を読んでみてほしい。更にはクイックソートの所を読んで、そこらに転がっているネットのページと読み比べてみてほしい。やっぱりクセが強い。でそのクセの強さがずっと続いていく。特に7章以降はもっとひどくなる。
ヒープソートやクイックソートを読んで、それでも良いという人が買えば良いと思う。
ちなみに解説を掲載した理由は、コードを理解できないと何が問題なのか分からないだろうと思ったからだ。まあ自分でもコメントが長くて読みにくいとは思う。（いや後から見るとなかなか読みやすいかもな、すぐ終わるし。これをグラフまでとネットワークフローアルゴリズムでやったら、基礎的なアルゴリズムの勉強なんて一瞬で終わるだろうに。選択基準も上の方に付けておいて）
　

import random

lst = list(range(20))
random.shuffle(lst)
print(lst)

ヒープソート

• 最大値を見つけて端と交換して、1つ小さなサイズで同じことをくり返していく選択ソートの効率の良い応用として、トーナメント方式でどれがどれより大きいのかを決めていく
• 二分木においては、親のインデックス*2 + 1に左の葉の値を、*2 + 2に右の葉の値を入れていく。例えば、根のインデックスは0で、その左の葉のインデックスが1、右の葉は2。更にその左の葉の左は3、右は4、という具合。考え方の問題だ。

def Heap_Sort(lst):
    list_size = len(lst)
    buildHeap(lst)   #ヒープ、つまり親要素は子要素より常に大きいか等しい（逆の場合もある）という制約を持つ木構造を作る。それで少なくともlst[0]が最大であることが保証される
    for i in reversed(range(list_size)):   #ここで処理の流れが変わる。今までは左に行くほど大きい傾向にあったが、最大であることが保証されたlst[0]から順に右端に移していく
        lst[0], lst[i] = lst[i], lst[0]   #buildHeapでどの子や孫より大きいことが保証されたlst[0]の値をlst[i]に移動する
        heapify(lst, 0, i)   #ここで非常に重要な処理が行われている。iはheapifyのmaxであり、maxとそれ以降は交換の対象にならない。逃しているようなイメージだ

def buildHeap(lst):
    list_size = len(lst)
    list_size_by2 = list_size // 2   #ちなみに、pythonにおいてはint（整数）の割り算（「//」）は端数を切り捨てで、奇数の場合が心配だったが、左右の葉は2倍+1と2倍+2なので問題無し
    for i in reversed(range(list_size_by2)):   #トーナメント方式で、末端の親から、親は子より大きいことを保証していく
        heapify(lst, i, list_size)

def heapify(lst, idx, max):   #3つの中で一番大きな数字が、idxの位置に納まる。更にidxの位置にあった新しい小さい値で同じことを行うことで、どの親も子や孫より大きいことが(もし今まで保証されていたなら)保証され続ける
    largest = idx   #一番大きいと仮定する
    left = 2 * idx + 1
    right = 2 * idx + 2

    if left < max and lst[left] > lst[idx]:   #leftがidxより大きい
        largest = left
    if right < max and lst[right] > lst[largest]:   #largestであることに注意。rightがどちらともより大きい
        largest = right
    if largest != idx:   #とにかくidxの位置が3つの中で一番大きいこと（親が子より大きいこと）が保証されればそれで良い。左右の関係は考える必要が無い
        lst[idx], lst[largest] = lst[largest], lst[idx]
        heapify(lst, largest, max)   #非常に分かりにくいが、idxにある値をlargestである右か左の位置に移した後に、その右か左の位置にあるidxにあった値で同じ処理を行う

Heap_Sort(lst)

print(lst)