Pythonヒープソート

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

このチュートリアルでは、Python でのヒープ ソート アルゴリズムの実装について説明します。

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

ヒープ ソートは、Python で配列とリストをソートするための堅牢なアルゴリズムです。 マージソートやクイックソートのように余分なスペースをとらず、とても速いので人気があります。

ヒープソートの時間計算量は O(n*log(n)) です。

ヒープ ソートは、データの中間状態を保存するためのデータ構造をこれ以上作成しないインプレース アルゴリズムです。 代わりに、元の配列に変更を加えます。

したがって、データが非常に大きい場合、これにより多くのスペースが節約されます。

このアルゴリズムの唯一の欠点は、非常に不安定なことです。 異なるインデックスで同じ値を持つ複数の要素が配列にある場合、並べ替え中にそれらの位置が変更されます。

ヒープ ソート アルゴリズムは、min または max heap のいずれかを再帰的に作成し、ルート ノードを取り出して配列内の最初の未ソートのインデックスに配置し、最後のヒープ要素をルート ノードに変換することによって機能します。

このプロセスは、ヒープ内に単一のノードが残るまで再帰的に繰り返されます。 最後に、最後のヒープ要素が配列の最後のインデックスに配置されます。

少し考えてみると、このプロセスは、最大値または最小値のいずれかを取得して、並べ替えられた配列の先頭に配置するため、選択並べ替えアルゴリズムに似ています。

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

最初に、元の配列、配列の長さ、および親ノードのインデックスを受け取る build_heap() 関数の実装を見ていきます。 ここで配列を見ると、最後の親ノードのインデックスは配列内の (n//2 - 1) にあります。

同様に、その特定の親の左の子のインデックスは 2*parent_index + 1 であり、右の子のインデックスは 2*parent_index + 2 です。

この例では、max-heap を作成しようとしています。 つまり、すべての親ノードはその子ノードよりも大きくする必要があります。

このために、最後の親ノードから開始し、ヒープのルート ノードまで上に移動します。 最小ヒープを作成する場合は、すべての親ノードを子ノードよりも小さくする必要があります。

この build_heap() 関数は、左または右の子が現在の親ノードよりも大きいかどうかをチェックし、最大のノードを親ノードと交換します。

この関数は、ヒープ内のすべての親ノードに対して前のプロセスを段階的に繰り返したいため、それ自体を再帰的に呼び出します。

次のコード スニペットは、前述の built_heap() 関数の Python での実用的な実装を示しています。

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)

これで、配列内の最大値を取り、それをヒープのルートに配置する関数ができました。 ソートされていない配列を受け取り、build_heap() 関数を呼び出し、ヒープから要素を抽出する関数が必要です。

次のコード スニペットは、Python での heapSort() 関数の実装を示しています。

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)

配列内で各親ノードの build_heap() 関数を段階的に呼び出します。 -1 のステップで、開始インデックスとして length//2-1 を、終了インデックスとして -1 を指定していることに注意してください。

これは、最後の親ノードから開始し、ルート ノードに到達するまでインデックスを 1 ずつ段階的に減らすことを意味します。

2 番目の for ループは、ヒープから要素を抽出します。 また、最後のインデックスから開始し、配列の最初のインデックスで停止します。

このループで配列の最初と最後の要素を交換し、ルート インデックスとして 0 を渡すことで、新しく並べ替えられた配列に対して build_heap() 関数を実行します。

これで、Python でヒープ ソートを実装するプログラムを作成できました。 配列をソートし、上記のコードをテストする時が来ました。

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

出力：

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

ご覧のとおり、配列は完全にソートされています。 これは、コードが正常に機能することを意味します。

降順で並べ替えたい場合は、上記で実装した max-heap の代わりに min-heap を作成できます。

最小ヒープとは何かについては、このチュートリアルの冒頭で既に説明しているため、この記事では最小ヒープについては説明しません。

私たちのプログラムは次のように動作します。 次のブロックは、コード実行の各段階での配列の状態を示しています。

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

ヒープには親ノードが 3つしかないため、build_heap() 関数は 3 回実行されます。

その後、要素抽出フェーズで最初の要素を取得し、それを最後の要素と交換して、build_heap() 関数を再度実行します。 このプロセスが length - 1 について繰り返され、配列がソートされます。