ヒープソート – 河内・水簾洞

１．調査内容

２．Pythonプログラムを調査して気づいた点

　・range命令に出会う
　　　数字のリストを作成したり、連番を生成してfor文で利用する
　　　　　便利な命令だと分かる

　・heap構造に出会う
　　　最も大きな数値を求めるのに有効なツリー構造だと分かる

　・再帰処理に出会う
　　　関数の中から自分自身を呼び出し、類似な処理を繰り返す
　　　　　最初は全然処理内容がトレースできず四苦八苦した

　　　眺めるだけではトレースできないと分かり、print文を挿入して解析する

　・Pythonでの変数の扱いルールに出会う
　　　関数の中で使われる変数はグローバル変数ではなくローカル変数
　　　　　引数として渡された値だけで処理を組み立てている
　　　　　同じ項目名が使えるのは、都度新しいプログラムが読込まれている
　　　　　　　※無限ループはメモリー不足になるとの注意が多く見られる
　　　　　　　
　　　＜ルール＞
　　　関数内で参照されるだけの変数は暗黙的にグローバルとなる
　　　関数の本体のどこかで値が変数に代入されたなら
　　　　　明示的にグローバルであると宣言されない限り、ローカルとみなす

３．資料集

def heapify(arr, n, i):
    largest = i  # 親ノードを最大値として初期化
    left = 2 * i + 1  # 左の子ノードのインデックス
    right = 2 * i + 2  # 右の子ノードのインデックス

    # 左の子ノードが親ノードより大きい場合、最大値を更新
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 右の子ノードが親ノードより大きい場合、最大値を更新
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 最大値が親ノードでない場合、親ノードと最大値を入れ替えて再帰的にheapifyを呼び出す
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapsort(arr):
    n = len(arr)

    # ヒープ木を構築（最初に一度、配列をヒープに変換）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 配列をヒープから取り出し、ソートを行う
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 最大値を配列の末尾に移動
        heapify(arr, i, 0)  # ヒープのサイズを減らして再度ヒープ化

# ソートするデータを用意
data = [64, 34, 25, 12, 22, 11, 90]
print("Before sorting: ", data)
heapsort(data)
print("After sorting: ", data)

1．生成ＡＩを利用してPythonプログラムを入手する　　　解析を始めるが、全く内容が頭に入ってこない
2．ネットでヒープソートを検索する　　　文章の説明だけでは理解が進まない
3．二分木のツリー構造に出会う　　　この構造をヒープ構造と呼ぶ、と分かる　　　１個の親に２個の子　　　親が一番大きい数値になる様に並べ替える
4．ツリー構造の考え方（順序づけ）の違いが分かる　　　・分類や検索で使うツリー構造　　　　　順番に下位の階層に進み　　　　　ヒットしなければ上位に上がって横に進む　　　　　① 　　　　　｜— ② 　　　　　｜　｜—③ 　　　　　｜　｜—④ 　　　　　｜—⑤ 　　　　　｜　｜—⑥ 　　　　　｜　｜—⑦
・ヒープソートで使うツリー構造　　　　　トップの位置からスタートし　　　　　下位に移り、左から順に進む　　　　　二分木の三角形を保って進む　　　　　①—②—③—④—⑤—⑥—⑦
5．三角形を使って数値の比較を行い、並べ替える　　　親が一番大きな数値になるように並べ替える
6．下位から始め、同列の処理が終われば上位へと移る　　　最終的にトップの位置に一番大きな数値が来る　　　トップの値を最後の位置にセットする　　　残された数値で同じことを繰り返し　　　　　トップの数値を下位から降順に並べる