Pythonヒープソート

このチュートリアルでは、ヒープ ソート アルゴリズムの仕組みと Python での実装方法を、ヒープ構築の背後にあるインデックス計算からサンプル リストのステップバイステップのトレースまで解説します。

Python のヒープ ソート アルゴリズム

ヒープ ソートは、リストを二分ヒープとして整理してソートする、比較ベースのアルゴリズムです。ヒープは、完全二分木を平坦な配列上の位置に格納したものです。最大ヒープ ではすべての親ノードがその子以上の値を持ち、最小ヒープ ではすべての親がその子以下の値を持ちます。

このアルゴリズムは、次の 2 つのフェーズを繰り返します。

1. 未ソートのデータからヒープを構築し、対象となる極値（最大ヒープでは最大値）がルートに来るようにします。
2. ルートをまだソートされていない領域の最後の要素と交換し、ヒープを 1 つ分縮小して、新しいルートでヒープ特性を復元します。

各繰り返しで 1 つの値が最終位置に確定し、ヒープ内にノードが 1 つだけ残るまで続きます。この点で、ヒープ ソートは選択ソートに似ています。各パスで現在の最大値を選び、未ソートのヒープ領域と配列のソート済みの末尾との間に配置します。

ヒープ ソートの時間計算量は、最良・平均・最悪のいずれの場合も O(n*log(n)) です。n 回の各抽出でヒープを復元するために最大 O(log n) の処理が必要になるためです。このソートは 2 つ目のデータ構造を構築する代わりに入力リストをインプレースで変更するため、大きな入力でもメモリ使用量を抑えられます。なお、以下に示す再帰的なヒープ修復関数は、コール スタック上で最大 O(log n) の補助領域を消費します。ふるい落とし（sift-down）ステップをループとして書き換えると、これを O(1) に削減できます。

ヒープ ソートの主な欠点は、安定ソートではないことです。同じ値を持つ要素が複数ある場合、ソート中にそれらの相対的な順序が変わる可能性があります。

Python でヒープ ソート アルゴリズムを実装する

実装は 2 つの関数に分かれます。build_heap() は 1 つの親ノードを起点としてその下のヒープ特性を修復し、heapSort() は構築フェーズと抽出フェーズを実行します。

build_heap() 関数は、配列、アクティブなヒープ領域の長さ、調べる親ノードのインデックスを受け取ります。平坦な配列では、最後の親ノードはインデックス length//2 - 1 にあり、親の左の子は 2*parent_index + 1、右の子は 2*parent_index + 2 にあります。

最大ヒープの場合、この関数は親を両方の子と比較し、子のほうが大きいときに大きいほうの子と交換します。交換によってさらに下位でヒープ特性が壊れる可能性があるため、build_heap() は影響を受けた部分木に対して自身を再帰呼び出しし、押し出された値が、その下のすべての親が再び有効になるまで沈み続けるようにします。

このセクションのコードと表示されるラベルや出力は英語のままです。

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2

    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index

    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index

    if largest_index != parent_index:
        arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]

        build_heap(arr, length, largest_index)

heapSort() 関数は、上で説明した 2 つのフェーズを実行します。最初のループは length//2 - 1 から 0 までのすべての親インデックスに対して build_heap() を呼び出し、配列全体を最大ヒープに変換します。2 番目のループは抽出を実行します。ルートを最後の未ソート位置に移し、アクティブ領域を縮め、インデックス 0 から再びヒープを修復します。

def heapSort(arr):
    length = len(arr)

    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)

    for element_index in range(length - 1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

次の完全なプログラムを実行して、サンプル リストをソートします。

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2

    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index

    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index

    if largest_index != parent_index:
        arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]

        build_heap(arr, length, largest_index)


def heapSort(arr):
    length = len(arr)

    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)

    for element_index in range(length - 1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)


arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

Sorted array : [1, 2, 3, 4, 5, 6]

配列は昇順に完全にソートされて返されます。出力ではラベル Sorted array : が英語のまま表示され、その右にソート済みの配列が続きます。同じ抽出パターンで降順にソートするには、最大ヒープの代わりに最小ヒープを構築します。build_heap() 内の 2 つの比較を反転させ、親が小さいほうの子と交換されるようにします。すると各抽出で現在の最小値が配列の末尾に確定し、降順の結果が得られます。

ヒープ ソートの例をトレースする

このプログラムを arr = [5, 3, 4, 2, 1, 6] に対して実行すると、次の状態が得られます。

• 入力: [5, 3, 4, 2, 1, 6]
• 構築パス 1（parent_index = 2）: [5, 3, 6, 2, 1, 4] — 値 4 が大きいほうの子 6 の下に沈みます
• 構築パス 2（parent_index = 1）: [5, 3, 6, 2, 1, 4] — 3 がすでに両方の子より大きいため、交換はありません
• 構築パス 3（parent_index = 0）: [6, 3, 5, 2, 1, 4] — 配列が有効な最大ヒープになります
• 抽出パス 1: [5, 3, 4, 2, 1, 6] — 6 が最後のインデックスに確定します
• 抽出パス 2: [4, 3, 1, 2, 5, 6]
• 抽出パス 3: [3, 2, 1, 4, 5, 6]
• 抽出パス 4: [2, 1, 3, 4, 5, 6]
• 抽出パス 5: [1, 2, 3, 4, 5, 6] — ソート完了

各抽出行は、そのパスの交換とヒープ修復後の状態を示しています。構築フェーズでは、6 要素のヒープに親ノードが 3 つあるため build_heap() を 3 回呼び出し、抽出フェーズでは length - 1 回ある交換・修復サイクルの各回で 1 回ずつ呼び出します。