この記事では、ヒープソート アルゴリズムについて説明します。ヒープ ソートは、指定された配列の要素を使用して最小ヒープまたは最大ヒープを作成することによって要素を処理します。 min-heap または max-heap は、ルート要素が配列の最小要素または最大要素を表す配列の順序を表します。
ヒープ ソートは基本的に 2 つの主要な操作を再帰的に実行します。
- 配列の要素を使用してヒープ H を構築します。
- 1で形成したヒープのルート要素を繰り返し削除セント段階。
ヒープソートについて詳しく知る前に、まずヒープソートの簡単な説明を見てみましょう。 ヒープ。
ヒープとは何ですか?
ヒープは完全なバイナリ ツリーであり、バイナリ ツリーはノードが最大 2 つの子を持つことができるツリーです。完全なバイナリ ツリーとは、最後のレベル、つまりリーフ ノードを除くすべてのレベルが完全に埋められ、すべてのノードが左寄せされるバイナリ ツリーです。
ヒープソートとは何ですか?
ヒープソートは、人気のある効率的なソート アルゴリズムです。ヒープ ソートの概念は、リストのヒープ部分から要素を 1 つずつ削除し、それらをリストのソート部分に挿入することです。
ヒープソートはインプレース並べ替えアルゴリズムです。
Cプログラムの文字列配列
次に、ヒープソートのアルゴリズムを見てみましょう。
アルゴリズム
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
BuildMaxHeap(arr)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
MaxHeapify(arr,i)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
ヒープソートアルゴリズムの仕組み
ここで、ヒープソート アルゴリズムの仕組みを見てみましょう。
ヒープ ソートでは、基本的に要素のソートに 2 つのフェーズが含まれます。ヒープソートアルゴリズムを使用すると、次のようになります。
- 最初のステップには、配列の要素を調整することによるヒープの作成が含まれます。
- ヒープの作成後、ヒープのルート要素を配列の最後に移動して繰り返し削除し、残りの要素を含むヒープ構造を保存します。
次に、例を使用してヒープソートの仕組みを詳しく見てみましょう。これをより明確に理解するために、ソートされていない配列を取得し、ヒープ ソートを使用してソートしてみます。説明がより明確かつ簡単になります。
まず、指定された配列からヒープを構築し、それを最大ヒープに変換する必要があります。
指定されたヒープを最大ヒープに変換した後の配列要素は -
次に、ルート要素を削除する必要があります (89) 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 （十一）。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 89 と 十一、 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、やはりルート要素を削除する必要があります。 (81) 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 (54)。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 81 と 54 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、ルート要素を削除する必要があります。 (76) 再び最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 (9)。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 76 と 9 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、再びルート要素を削除する必要があります。 (54) 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 (14)。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 54 と 14 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、再びルート要素を削除する必要があります。 (22) 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 （十一）。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 22 と 十一 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、再びルート要素を削除する必要があります。 (14) 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 (9)。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 14 と 9 ヒープを最大ヒープに変換すると、配列の要素は次のようになります。
次のステップでは、再びルート要素を削除する必要があります。 （十一） 最大ヒープから。このノードを削除するには、最後のノードと交換する必要があります。 (9)。 ルート要素を削除した後、再度ヒープ化して最大ヒープに変換する必要があります。
配列要素を交換した後 十一 と 9、 配列の要素は -
現在、ヒープには要素が 1 つだけ残っています。削除するとヒープは空になります。
ソートが完了すると、配列要素は次のようになります -
ラテックス部分導関数
これで、配列が完全にソートされました。
ヒープソートの複雑さ
ここで、ヒープソートの時間計算量を最良のケース、平均的なケース、最悪のケースで見てみましょう。ヒープソートの空間の複雑さも見ていきます。
1. 時間計算量
| 場合 | 時間計算量 |
|---|---|
| 最良の場合 | O(n ログ) |
| 平均的なケース | O(n log n) |
| 最悪の場合 | O(n log n) |
ヒープソートの時間計算量は次のとおりです。 O(n ログ) 3 つのケースすべて (最良のケース、平均的なケース、最悪のケース)。 n 個の要素を持つ完全な二分木の高さは次のとおりです。 落ち着いた。
2. 空間の複雑さ
| 空間の複雑さ | ○(1) |
| 安定した | N0 |
- ヒープソートの空間複雑さは O(1) です。
ヒープソートの実装
ここで、さまざまなプログラミング言語でのヒープソートのプログラムを見てみましょう。
プログラム： C言語でヒープソートを実装するプログラムを書きます。
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>