heap sort c with examples
例を使用したヒープソートの概要。
ヒープソートは、最も効率的なソート手法の1つです。この手法では、指定されたソートされていない配列からヒープを構築し、そのヒープを再度使用して配列をソートします。
ヒープソートは、比較に基づくソート手法であり、バイナリヒープを使用します。
=> Easy C ++トレーニングシリーズをお読みください。
c ++選択ソートアルゴリズム
学習内容:
バイナリヒープとは何ですか?
バイナリヒープは、完全なバイナリツリーを使用して表されます。完全な二分木は、各レベルのすべてのノードが葉のノードを除いて完全に満たされ、ノードが左端にある二分木です。
バイナリヒープまたは単にヒープは、ルートノードがその2つの子ノードよりも大きくなるようにアイテムまたはノードが格納される完全なバイナリツリーです。これは、最大ヒープとも呼ばれます。
バイナリヒープ内のアイテムは、ルートノードがその2つの子ノードよりも小さい最小ヒープとして格納することもできます。ヒープは二分木または配列として表すことができます。
ヒープを配列として表す場合、インデックスが0から始まると仮定すると、ルート要素は0に格納されます。一般に、親ノードが位置Iにある場合、左側の子ノードは位置(2 * I + 1)そして右側のノードは(2 * I +2)にあります。
一般的なアルゴリズム
以下に示すのは、ヒープソート手法の一般的なアルゴリズムです。
- ルートがヒープの最も高い要素になるように、指定されたデータから最大ヒープを構築します。
- ルート、つまりヒープから最も高い要素を削除し、ヒープの最後の要素と置き換えるか交換します。
- 次に、最大ヒープのプロパティに違反しないように(heapify)、最大ヒープを調整します。
- 上記の手順により、ヒープサイズが1つ減少します。
- ヒープサイズが1に減少するまで、上記の3つの手順を繰り返します。
特定のデータセットを昇順で並べ替える一般的なアルゴリズムに示されているように、最初に特定のデータの最大ヒープを構築します。
次のデータセットを使用して最大ヒープを構築する例を見てみましょう。
6、10、2、4、1
このデータセットのツリーは次のように構築できます。
上記のツリー表現では、括弧内の数字は配列内のそれぞれの位置を表しています。
上記の表現の最大ヒープを構築するには、親ノードがその子ノードよりも大きくなければならないというヒープ条件を満たす必要があります。つまり、ツリーを最大ヒープに変換するために、ツリーを「ヒープ化」する必要があります。
上記のツリーをヒープ化すると、次のように最大ヒープが取得されます。
上に示したように、この最大ヒープは配列から生成されます。
次に、ヒープソートの図を示します。 max-heapの構築を見てきましたが、max-heapを構築するための詳細な手順をスキップし、各ステップでの最大ヒープを直接示します。
図
次の要素の配列について考えてみます。ヒープソート手法を使用して、この配列をソートする必要があります。
ソートする配列について、以下に示すように最大ヒープを作成しましょう。
ヒープが構築されたら、次に示すように配列形式でヒープを表します。
今、私たちは1を比較しますstノード(ルート)を最後のノードと交換してから交換します。したがって、上記のように、17と3を入れ替えて、17が最後の位置にあり、3が最初の位置にあるようにします。
次に、ノード17をヒープから削除し、以下の影付きの部分に示すように、ソートされた配列に配置します。
ここで、配列要素のヒープを再度作成します。今回は、ヒープから1つの要素(17)を削除したため、ヒープサイズが1つ減少します。
残りの要素のヒープを以下に示します。
次のステップでは、同じステップを繰り返します。
ルート要素とヒープ内の最後の要素を比較して交換します。
スワップ後、要素12をヒープから削除し、ソートされた配列にシフトします。
もう一度、以下に示すように、残りの要素の最大ヒープを作成します。
ここで、ルートと最後の要素、つまり9と3を交換します。交換後、要素9はヒープから削除され、並べ替えられた配列に配置されます。
この時点で、以下に示すように、ヒープには3つの要素しかありません。
6と3を交換し、要素6をヒープから削除して、ソートされた配列に追加します。
次に、残りの要素のヒープを作成してから、両方を相互に交換します。
Windows7用の無料のジャンクファイルクリーナー
4と3を交換した後、要素4をヒープから削除し、ソートされた配列に追加します。これで、以下に示すように、ヒープに残っているノードは1つだけになります。 。
したがって、ノードが1つだけ残っているので、ヒープからノードを削除して、並べ替えられた配列に追加します。
したがって、上記の例は、ヒープソートの結果として取得したソート済み配列です。
上の図では、配列を昇順で並べ替えています。配列を降順で並べ替える必要がある場合は、同じ手順を実行する必要がありますが、最小ヒープを使用します。
ヒープソートアルゴリズムは、最小の要素を選択してソートされた配列に配置する選択ソートと同じです。ただし、パフォーマンスに関する限り、ヒープソートは選択ソートよりも高速です。ヒープソートは選択ソートの改良版であるため、これを置くことができます。
次に、ヒープソートをC ++およびJava言語で実装します。
両方の実装で最も重要な関数は、「ヒープ化」関数です。この関数は、ノードが削除されたとき、またはmax-heapが構築されたときに、サブツリーを再配置するためにメインヒープソートルーチンによって呼び出されます。
ツリーを正しくヒープ化すると、適切な位置に正しい要素を取得できるようになり、配列が正しく並べ替えられます。
C ++の例
以下は、ヒープソート実装のC ++コードです。
#include using namespace std; // function to heapify the tree void heapify(int arr[], int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr[root], arr[largest]); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr[], int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr[], int n) { for (int i=0; i 出力:
入力配列
4 17 3 12 9 6
アンドロイドのための最高の音楽ダウンローダーは何ですか
ソートされた配列
3 4 6 9 12 17
次に、Java言語でヒープソートを実装します
Javaの例
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr[]) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr[], int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != root) { int swap = arr[root]; arr[root] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr[]) { int n = arr.length; for (int i=0; i 出力:
入力配列:
4 17 3 12 9 6
ソートされた配列:
3 4 6 9 12 17
結論
ヒープソートは、バイナリヒープを使用した比較ベースのソート手法です。
これらの並べ替え手法はどちらも、配列内の最大または最小の要素を繰り返し検索し、それを並べ替えられた配列に配置するという同様のロジックで機能するため、選択並べ替えの改善と言えます。
ヒープソートは、max-heapまたはmin-heapを使用して配列をソートします。ヒープソートの最初のステップは、配列データから最小または最大ヒープを構築してから、ルート要素を再帰的に削除し、ヒープ内にノードが1つだけ存在するまでヒープをヒープ化することです。
ヒープソートは効率的なアルゴリズムであり、選択ソートよりも高速に実行されます。これは、ほぼソートされた配列をソートしたり、配列内のk個の最大または最小の要素を検索したりするために使用できます。
これで、C ++での並べ替え手法に関するトピックが完了しました。次のチュートリアル以降、データ構造を1つずつ開始します。
=> ここでC ++トレーニングシリーズ全体を探してください。
推奨読書