LoginSignup
0

More than 1 year has passed since last update.

ヒープソートの理解

Posted at

ソートアルゴリズムには、選択ソート、挿入ソート、マージソート、バブルソート、ヒープソートなどがあるが、その中で最も理解に苦しんだヒープソートをPythonで整理していく。

ヒープとは

ヒープソートに用いられるヒープは木構造であり、子ノードの値は、親ノードの値以上である性質を持つ。この場合、ルートの値は最小値になり、最小値の探索が簡単になる。逆に、子ノードの値が親ノードの値以下の場合もあり、ルートの値は最大値になる。親ノードが最大2つの子ノードを持つ構成を二分ヒープ木という。

ヒープソートの実装

子ノードの値が親ノードの値以上の場合で実装していく。
二分ヒープ木をリストで構成する時、ある位置のインデックス番号が0の場合、左の子ノードのインデックス番号は1、右の子ノードのインデックス番号は2になる。つまり、ある位置のインデックス番号がnの場合、左の子ノードのインデックス番号は2n + 1、右の子ノードのインデックス番号は2n + 2になる。また、親ノードは(n - 1) // 2になる。

ヒープを構成

数字がまばらに格納されるリストを昇順にソートしていく。
リスト([3,6,1,4,8,2])があり、そのリストでヒープを構成する。現在の位置がルートでない、または値が親より大きい間は、親と交換し、位置を親の位置に移動する。

Python
data = [3, 6, 1, 4, 8, 2]

# ヒープを構成
for i in range(len(data)):
    pos = i
    # 現在の位置がルートでない、または値が親より大きい間は、親と交換し、位置を親の位置に移動
    while (pos > 0) and (data[(pos - 1) // 2] < data[pos]):
        data[(pos - 1) // 2], data[pos] = data[pos], data[(pos - 1) // 2]
        pos = (pos - 1) // 2
        print(data)
実行結果
[6, 3, 1, 4, 8, 2]
[6, 4, 1, 3, 8, 2]
[6, 8, 1, 3, 4, 2]
[8, 6, 1, 3, 4, 2]
[8, 6, 2, 3, 4, 1]
[8, 6, 2, 3, 4, 1]

ヒープソートを実行

現在の位置の値をヒープの先頭と交換する。左下の値の方が大きい場合、左下と交換し、右下の値の方が大きい場合、右下と交換する。これを繰り返していくとリストの値が昇順にソートされる。

Python
for i in range(len(data), 0, -1):
    data[i - 1], data[0], = data[0], data[i - 1]
    # ヒープの先頭から開始
    pos = 0
    while ((pos * 2 + 1 < i - 1) and (data[pos] < data[pos * 2 + 1])) or (
        (pos * 2 + 2 < i - 1) and (data[pos] < data[pos * 2 + 2])):
        # 左下の値の方が大きい場合、左下と交換
        if (pos * 2 + 2 == i - 1) or (data[pos * 2 + 1] > data[pos * 2 + 2]):
            data[pos], data[pos * 2 + 1] = data[pos * 2 + 1], data[pos]
            pos = pos * 2 + 1
        # 右下の値の方が大きい場合、右下と交換
        else:
            data[pos], data[pos * 2 + 2] = data[pos * 2 + 2], data[pos]
            pos = pos * 2 + 2
        print(data)

print(data)
実行結果
[6, 1, 2, 3, 4, 8]
[6, 4, 2, 3, 1, 8]
[4, 1, 2, 3, 6, 8]
[4, 3, 2, 1, 6, 8]
[3, 1, 2, 4, 6, 8]
[1, 2, 3, 4, 6, 8]

最後に

ヒープソートにはupheapdownheapも存在するが、今回は省略。
まだあやふやなところがあるので、何度も見直して理解を深めたい。
間違い等があればご指摘お願いいたします。

参考

増井 敏克「Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量」 翔泳社 2020年1月24日

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0