ヒープソートアルゴリズム（コード付き） Python 　 C++)

替え： サラ・チェン サラ・チェン
Hours 更新中

ヒープソートアルゴリズムとは何ですか?

ヒープ ソートは、人気があり高速なソート アルゴリズムの 1 つです。完全なバイナリ ツリー データ構造に基づいて構築されています。最大要素を検索し、最大ヒープの最上部に配置します。バイナリ ツリーの親ノードに配置します。

配列が与えられたとします。 データ = [10,5, 7, 9, 4, 11, 45, 17, 60].

配列内で、i 番目 (i=0,1,2,3 …) のインデックスが親ノードの場合、(2i+1) と (2i+2) は左右の子になります。 この配列を使用して完全なバイナリ ツリーを作成すると、次のようになります。

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

配列の最初から最後までヒープ化プロセスを実行します。最初に、配列をツリーに変換すると、上記のようになります。ヒーププロパティ (最小ヒープまたは最大ヒープ) が維持されていないことがわかります。すべてのノードに対してヒープ化プロセスを実行すると、ソートされた配列が取得されます。

ヒープソートの応用

ヒープ ソート アルゴリズムの使用例をいくつか示します。

  • 「プライオリティキュー」の構築にはヒープソートが必要です。 ヒープソートでは、挿入が行われるたびに要素がソートされた状態が維持されるためです。
  • ヒープ データ構造は、k を見つけるのに効率的です。th 指定された配列内の最大の要素。
  • Linux カーネルはデフォルトとしてヒープ ソートを使用します 並べ替えアルゴリズム 空間計算量はO(1)である。

例によるヒープソートの作成

ここでは、次の完全二分木から最大ヒープを構築します。

例によるヒープソートの作成

リーフ ノードは 17、60、4、11、45 です。これらには子ノードがありません。これがリーフ ノードである理由です。したがって、親ノードからヒープ化メソッドを開始します。手順は次のとおりです。

ステップ1） 一番左のサブツリーを選択します。 子ノードの方が大きい場合は、親ノードと子ノードを交換します。

ここでは、親ノードは 9 です。子ノードは 17 と 60 です。60 が最大であるため、60 と 9 は交換され、 最大ヒープ.

例によるヒープソートの作成

ステップ2） これで、一番左のサブツリーがヒープ化されました。 次の親ノードは 7 です。この親には 45 つの子ノードがあり、最大のものは 45 です。したがって、7 と XNUMX が交換されます。

例によるヒープソートの作成

例によるヒープソートの作成

ステップ3） ノード60とノード4は親ノード5を持っています。「5」は子ノード60より小さいので交換されます。

例によるヒープソートの作成

例によるヒープソートの作成

ステップ4） 現在、ノード 5 には子ノード 17,9 があります。 これは最大ヒーププロパティを維持しません。 したがって、5 は 17 に置き換えられます。

例によるヒープソートの作成

ステップ5） ノード 10 は 60 とスワップされ、次に 17 とスワップされます。プロセスは次のようになります。

例によるヒープソートの作成

例によるヒープソートの作成

ステップ6） ステップ 5 までで、最大ヒープを作成しました。 すべての親ノードはその子ノードよりも大きくなります。 ルート ノードの最大値は (60) です。

注意： ソートされた配列を作成するには、最大値ノードを後続ノードに置き換える必要があります。

このプロセスは「」と呼ばれます。最大抽出”。 60 が最大ノードなので、その位置を 0 番目のインデックスに固定し、ノード 60 なしでヒープを作成します。

例によるヒープソートの作成

例によるヒープソートの作成

ステップ7） 60 が削除されると、次の最大値は 45 になります。ノード 45 から「最大値の抽出」プロセスを再度実行します。

今回は 45 を取得し、ルート ノードをその後継の 17 に置き換えます。

「私たちは実行する必要があります」最大抽出すべての要素がソートされるまで。

すべての最大値を抽出するまでこれらの手順を実行すると、次の配列が得られます。

例によるヒープソートの作成

関連記事

バイナリヒープとは何ですか?

バイナリ ヒープは一種の完全なヒープです。 二分木 データ構造。 この種のツリー構造では、親ノードは子ノードより大きいか小さいかのいずれかです。 親ノードが小さい場合、ヒープは「最小ヒープ」と呼ばれ、親ノードが大きい場合、ヒープは「最大ヒープ」と呼ばれます。

最小ヒープと最大ヒープの例を次に示します。

最小ヒープと最大ヒープ
最小ヒープと最大ヒープ

上の図で、「最小ヒープ」に注目すると、親ノードは常に子ノードよりも小さくなります。 ツリーの先頭で、最小値 10 が見つかります。

同様に、「最大ヒープ」の場合、親ノードは常に子ノードよりも大きくなります。 最大要素は「最大ヒープ」のヘッド ノードに存在します。

「Heapify」とは何ですか？

「Heapify」とは、ノードの位置を保証するヒープの原理です。Heapify では、最大ヒープは常に親と子の関係を維持し、親ノードは子ノードよりも大きくなります。

たとえば、新しいノードが追加された場合、ヒープの形状を変更する必要があります。ただし、ノードを変更または交換したり、配列を再配置したりする必要がある場合もあります。ヒープの形状を変更するこのプロセスは、「ヒープ化」と呼ばれます。

heapify がどのように動作するかの例を次に示します。

新しいノードとHeapifyの追加
新しいノードを追加してヒープ化する

heapify の手順は次のとおりです。

ステップ1） ノード 65 をノード 60 の右側の子として追加しました。

ステップ2） 新しく追加されたノードが親よりも大きいかどうかを確認します。

ステップ3） これは親ノードよりも大きいため、右側の子をその親と交換しました。

ヒープの構築方法

ヒープを構築したりツリーをヒープ化したりする前に、それをどのように保存するかを知る必要があります。ヒープは完全な二分木なので、 配列 ヒープのデータを保持します。

配列に合計 n 個の要素が含まれているとします。 「i」番目のインデックスが親ノードの場合、左側のノードがインデックスになります。 (2i+1)、右のノードがインデックスになります (2i+2)。 配列のインデックスは 0 から始まると想定しています。

これを使用して、最大ヒープを次のように配列のようなものに格納してみましょう。

最大ヒープの配列ベースの表現
最大ヒープの配列ベースの表現

ヒープ化アルゴリズムはヒープ プロパティを維持します。親に極端な値 (小さいか大きい) がない場合、最も極端な子ノードと交換されます。

最大ヒープをヒープ化する手順は次のとおりです。

ステップ1） リーフノードから開始します。

ステップ2） 親と子の間の最大値を見つけます。

ステップ3） 子ノードの値が親ノードよりも大きい場合は、ノードを交換します。

ステップ4） XNUMX つ上のレベルに進みます。

ステップ5） インデックス 2,3,4 に到達するまで、またはツリー全体をソートするまで、ステップ 0、XNUMX、XNUMX を実行します。

再帰ヒープ化 (最大ヒープ) の疑似コードは次のとおりです。

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

ヒープソートの疑似コード

ヒープソートアルゴリズムの疑似コードは次のとおりです。

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

ヒープソートコードの例 C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

出力：

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

ヒープソートコードの例 Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

出力：

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

ヒープソートの時間と空間の計算量分析

ヒープソートでは、時間計算量と空間計算量を分析できます。時間計算量については、次のケースがあります。

  1. 最良の場合
  2. 平均的なケース
  3. 最悪の場合

ヒープは完全なバイナリ ツリー上に実装されます。 したがって、バイナリ ツリーの最下位レベルには最大数のノードが存在します。 最下位レベルに n 個のノードがある場合、上のレベルには n/2 個のノードがあります。

時間と空間の複雑さの分析

この例では、レベル 3 には 2 つの項目があり、レベル 1 には XNUMX つの項目があり、レベル XNUMX には XNUMX つの項目があります。 アイテムが合計 n 個ある場合、高さまたは合計レベルは次のようになります。 歳入録2（n）。 したがって、単一の要素を挿入するには、最大で Log(n) 回の反復が必要になる可能性があります。

ヒープから最大値を取りたいときは、ルートノードを取ります。そして、再びヒープ化を実行します。各ヒープ化は 歳入録2（n） 時間。 最大値の抽出には O(1) 時間がかかります。

ヒープソートアルゴリズムのベストケースの時間計算量

すべての要素が配列内ですでにソートされている場合、ヒープの構築には O(n) 時間がかかります。 リストがソートされている場合、項目の挿入には O(1) という一定の時間がかかるためです。

したがって、最大ヒープまたは最小ヒープを作成するには、最良の場合でも O(n) 時間がかかります。

ヒープソートアルゴリズムの平均ケース時間計算量

アイテムを挿入したり最大値を取り出すにはO(log(n))の時間がかかります。したがって、ヒープソートアルゴリズムの平均ケース時間計算量は次のようになります。 O(n log(n))。

ヒープソートアルゴリズムの最悪ケースの時間計算量

平均的なケースと同様に、最悪のシナリオではヒープ化をn回実行する必要があるかもしれません。ヒープ化にはそれぞれO(log(n))の時間がかかります。したがって、最悪の場合の時間計算量は次のようになります。 O(n log(n))。

ヒープソートアルゴリズムの空間計算量

ヒープソートは、インプレースで設計されたアルゴリズムです。つまり、タスクを実行するために余分なメモリや一時メモリは必要ありません。実装を見ると、ノードの交換を実行するために swap() を使用していることがわかります。他のリストや配列は必要ありませんでした。したがって、空間計算量は O(1) です。