Javaでのヒープソート

Java のヒープソートは比較ベースのソート手法であり、データ構造のバイナリ ヒープが使用されます。このソートは選択ソートとほぼ同じで、最大の要素が選択され、最後に配置され、すべての要素に対してこのプロセスが繰り返されます。ヒープ ソートを理解するために、Java におけるバイナリ ヒープ ソートがどのようなものかを見てみましょう。

• ツリーベースのデータ構造。
• 完全なバイナリ ツリー。
• 最大 2 人の子供を持つことができます。
• ルート ノードの値は大きくすることも (最大ヒープ)、小さくすることもできます (最小ヒープ)

Java ではヒープ ソートはどのように機能しますか?

アルゴリズムに進む前に、Heapify とは何かを見てみましょう。

広告 このカテゴリーの人気コース JAVA マスタリー - スペシャライゼーション | 78 コース シリーズ | 15 回の模擬テスト

ヒーピファイ

入力データを使用してヒープが作成された後、ヒープのプロパティが満たされない可能性があります。これを実現するには、heapify という関数を使用してヒープ ノードを調整します。最大ヒープを作成する場合は、現在の要素がその子と比較され、子の値が現在の要素より大きい場合、左または右の子の最大の要素との交換が行われます。同様に、最小ヒープを作成する必要がある場合、左または右の子の最小要素を使用してスワップが行われます。たとえば、次は入力配列です。

これを配列ではなくツリーとみなすことができます。最初の要素がルートになります。 2 番目はルートの左の子になります。 3 番目の要素はルートの右側の子となり、以下同様となります。

ヒープをツリーに変換するには、ツリーをボトムアップ方向に走査します。リーフノードには子がないので、次のレベルを調べてみましょう。つまり、5 と 7 です。

左側にあるように、5時に開始できます。ここで、5 には 9 と 4 という 2 つの子があります。9 は親ノード 5 よりも大きいです。親を大きくするには、5 と 9 を交換します。交換後のツリーは次のようになります。

次の要素 7 に進みましょう。ここで、8 と 2 は子です。要素 9 と 4 と同様に、7 と 8 は以下のツリーのように交換されます。

最後に、3 には 2 つの子 (9 と 8) があり、子とルートの中で 9 の方が大きくなります。したがって、根を大きくするために 3 と 9 を交換します。以下に示すように、有効なヒープが形成されるまでプロセスを繰り返します。

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

1. 入力データを使用して Max ヒープを作成します
2. 最後の要素をヒープ内の最大の要素に置き換えます
3. 木を盛り上げる
4. 配列がソートされるまでプロセスを繰り返します

ヒープを降順でソートするアルゴリズム

1. 入力データを使用して最小ヒープを作成します
2. 最後の要素をヒープ内の最小の要素に置き換えます
3. 木を盛り上げる
4. 配列がソートされるまでプロセスを繰り返します

ここで、指定されたアルゴリズムを使用して、上記で取得したヒープを昇順にソートしてみましょう。まず、最大の要素を削除します。つまり、ルート化して最後の要素に置き換えます。

次に、以下に示すように、形成されたツリーをヒープ化し、削除された要素を配列の最後に挿入します。

再度、ルート要素を削除し、最後の要素に置き換えて Heapify します。

削除した要素を空いた位置に挿入します。これで、配列の末尾がソートされていることがわかります。

次に、要素 7 を削除し、要素 2 に置き換えます。

以下に示すように、ツリーを積み上げます。

配列がソートされるまでこのプロセスを繰り返します。要素 5.

を削除します。

木を盛り上げます。

要素 4 を削除します。

また山盛りです。

最終的には、このようなソートされた配列が形成されます。

例

それでは、Java でのヒープ ソートのソース コードを見てみましょう

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild  = 2*i + 1; // index of left child = 2*i + 1
int rightChild  = 2*i + 2; //index of right child  = 2*i + 2
// left child is greater than root
if (leftChild  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

出力

結論

ヒープ ソートは、バイナリ ヒープ データ構造に依存するソート手法です。これは選択ソートにほぼ似ており、ソートとヒープに別個の配列を使用しません。

おすすめ記事

これは Java でのヒープ ソートのガイドです。ここでは、昇順と降順を使用した実際の並べ替えアルゴリズムとサンプル コードの例について説明します。詳細については、他のおすすめ記事を参照することもできます –

1. Java でのマージソート
2. C でのヒープソート
3. C++ でのヒープ ソート
4. データ構造内の選択ソート

以上がJavaでのヒープソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。