古典的なソートアルゴリズムヒープソートの簡単な分析

ヒープは通常、(完全な) ツリーとして表示できるオブジェクトの配列です。そして、以下のルールは常に満たされます。

ヒープは完全な二分木である

ノードは常にその子ノードよりも大きくなります (または小さくなります)。

したがって、2 番目の特性に従って、バイナリ ヒープは最大ヒープ (または最大ヒープ) と最小ヒープ (または最小ヒープ) に分割されます。

上の図では、1 2 は大きなトップヒープ、3 4 は小さなトップヒープです。ヒープかどうかを判断する条件: 「ルート ノードから任意のノードまでのパス上のノード シーケンスの順序です。シーケンスが順序どおりか逆順かは、max-heap と min-heap によって決まります。」

Python は「ヒープ」データ型を提供しておらず、リストを直接ヒープとして扱います。 Pythonが提供するheapqパッケージは、ヒープ操作を実行するためのツール機能を提供するいくつかの関数を提供します。

 >>> heapq をインポートする
>>> ヒープq.__すべて__
 [ 'heappush' 、 'heappop' 、 'heapify' 、 'heapreplace' 、 'merge' 、 'nlargest' 、 'nsmallest' 、 'heappushpop' ]

ヒープソート

ヒープ内に要素を挿入した後、その要素が再びヒープの特性を満たすように調整する必要があります。このプロセスは、ヒープ化と呼ばれます。

では、ヒープソートの基本的な考え方は何でしょうか?

1. ソートするシーケンスをヒープH[0...n-1]に構築し、（昇順と降順の要件）に従って大きなトップヒープまたは小さなトップヒープを選択します。
2. ヒープの先頭 (最大値) と末尾を交換します。
3. ノードが配置されているパスを上または下にたどり、比較してから交換します。目的は、新しい配列の先頭データを対応する位置に調整することです。

次に例を示します (リソースは Wang Zheng のアルゴリズムから取得)。たとえば、上記の最大ヒープにデータ 22 を追加します。

ヒープ化は非常に簡単で、ノードがあるパスを上または下に移動し、比較して交換するだけです。

ヒープソートの削除操作は、通常、ヒープの最上位要素を参照します。ヒープの最上位要素を削除した後、2 番目に大きい要素をヒープの最上位に配置する必要があります。すると、2 番目に大きい要素が必ず左と右の子ノードに表示されます。

次に、2 番目に大きいノードを繰り返し削除し、リーフ ノードが削除されるまでこれを繰り返します。しかし、これによりアレイ ホールの問題が発生します。

したがって、ここでもう 1 つのトリックがあります。つまり、ヒープの最上位要素を削除するときに、直接削除することはできません。ヒープの最上位要素を最後の要素と交換し、条件が満たされるまでヒープの特性に応じてヒープを調整する必要があります。

ソート処理では、ソートするシーケンスの長さから毎回 1 を減算し、次にこれら 2 つの手順を実行します。

以下は、Python の heapq モジュールを使用して実装されたヒープソートの簡単なコードです。

 heapqからheappop、heappush をインポートします
 
 def heap_sort(配列):
    ヒープ = []
配列内の要素の場合:
        heappush(ヒープ、要素) 
 
    注文 = [] 
 
    ヒープ中:
        順序付けられた追加(ヒープポップ(ヒープ))
返品注文
 
配列 = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
 print(heap_sort(配列))
 # [2、4、5、13、15、17、18、21、24、26]

heapq モジュールを使用しない場合は、プッシュ ソートのヒープ ソートにおけるヒープ構築プロセスを理解する必要があります。

配列をその場でヒープに構築します。別の配列を使用せずに元の配列を操作します。ヒープを構築するには 2 つの方法があります。

ヒープ構築の最初の方法は、配列データを前から後ろへ処理し、各データがヒープ内に挿入されるときに下から上に積み重ねられることです。 2 番目の実装アイデアは、配列を後ろから前に処理し、各データを上から下に積み重ねることです。

• 補足: レベル順トラバーサル(前方-中間-後方トラバーサル方式もあります)を使用して配列にマッピングした後、ツリーまたはサブツリーのルートノードがarr[root]であると仮定すると、対応する子ノードはそれぞれarr[root*2+1]、arr[root*2+2]になります。

つまり、ノードの添字が i の場合、左の子ノードの添字は 2∗i+1、右の子ノードの添字は 2∗i+2、親ノードの添字は となります。

 def heap_sort(配列):
    n = len(配列)
    # 子ノードが順番に並んでいることを確認するために、ヒープを最後から構築します
iが範囲((n-1)//2, -1, -1)内にある場合:
        _shift(配列, n, i)
    # ヒープの先頭の要素を順番に末尾にスワップし、ヒープの先頭を再構築します (ヒープにはスワップした最大の要素は含まれません)
 iが範囲(n-1, 0, -1)内にある場合:
        配列[0]、配列[i] = 配列[i]、配列[0]
        _shift(配列, i, 0)
配列を返す
 
 # ヒープの最上位要素を再構築します。n: ヒープ要素の数、i: ヒープの最上位位置
def _shift(配列, n, i):
    # 子ノードがない場合は直接戻ります
    i*2+1 >= nの場合:
戻る 
    # 子ノードの最大位置を取得する
    maxsub = i*2+2、i*2+2 < nかつarray[i*2+1] <= array[i*2+2] の場合、それ以外の場合はi*2+1
    # ノードが最大の子ノードよりも小さい場合は、要素を交換し、子ノードを先頭としてヒープを再帰的に再構築します。
    配列[i] < 配列[maxsub]の場合:
        配列[i]、配列[maxsub] = 配列[maxsub]、配列[i]
        _shift(配列, n, 最大サブ) 
 
 __name__ == '__main__'の場合:
    配列 = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
    print(heap_sort(配列)) 
     
 # [2、4、5、13、15、17、18、21、24、26]

ヒープソートは、ソート処理中にヒープの最後のノードとヒープの最上位ノードを交換する操作があるため、同じ値を持つデータの元の相対順序が変更される可能性があるため、安定したソートアルゴリズムではありません。ヒープソートの全体的な時間計算量は O(nlogn) です。

参考資料 https://github.com/MaoliRUNsen/runsenlearnpy100