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