C＃でのヒープソート

ヒープソートは、ヒープデータ構造を利用するソートアルゴリズムです。ヒープのルート要素、つまり最大の要素が削除され、配列に格納されるたびに。右端のリーフ要素に置き換えられ、ヒープが再確立されます。これは、ヒープに要素がなくなるまで実行され、配列が並べ替えられます。

C＃でのヒープソートを示すプログラムは次のとおりです。

例

using System;
namespace HeapSortDemo {
   public class example {
      static void heapSort(int[] arr, int n) {
         for (int i = n / 2 - 1; i >= 0; i--)
         heapify(arr, n, i);
         for (int i = n-1; i>=0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
         }
      }
      static void heapify(int[] arr, int n, int i) {
         int largest = i;
         int left = 2*i + 1;
         int right = 2*i + 2;
         if (left < n && arr[left] > arr[largest])
         largest = left;
         if (right < n && arr[right] > arr[largest])
         largest = right;
         if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
         }
      }
      public static void Main() {
         int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
         int n = 10, i;
         Console.WriteLine("Heap Sort");
         Console.Write("Initial array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
         heapSort(arr, 10);
         Console.Write("\nSorted Array is: ");
         for (i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
         }
      }
   }
}

出力

上記のプログラムの出力は次のとおりです。

Heap Sort
Initial array is: 55 25 89 34 12 19 78 95 1 100
Sorted Array is: 1 12 19 25 34 55 78 89 95 100

それでは、上記のプログラムを理解しましょう。

関数main（）には、配列arrが含まれています。初期配列を出力してから、配列をソートする関数heapSort（）を呼び出します。これは、次のコードスニペットで確認できます。

int[] arr = {55, 25, 89, 34, 12, 19, 78, 95, 1, 100};
int n = 10, i;
Console.WriteLine("Heap Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}
heapSort(arr, 10);

関数heapSort（）は、最初に指定された要素をヒープに変換します。これは、forループを使用し、ヒープのすべての非リーフ要素に対して関数heapify（）を呼び出すことによって行われます。これは、次のコードスニペットで確認できます。

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

ヒープが作成された後、forループを使用して、ヒープのルート要素、つまり最大の要素を削除します。これは右端のリーフ要素に置き換えられ、ヒープを再確立するためにheapify（）が再度呼び出されます。これは、次のコードスニペットで確認できます。

for (int i = n-1; i>=0; i--) {
   int temp = arr[0];
   arr[0] = arr[i];
   arr[i] = temp;
   heapify(arr, i, 0);
}

関数heapify（）は、必要に応じて要素を配置することにより、ヒープ構造を作成します。このプロセスは、インデックスiの要素から始まります。これは、heapify（）関数のルート要素と見なされます。これは、次のコードスニペットで確認できます。

int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
   int swap = arr[i];
   arr[i] = arr[largest];
   arr[largest] = swap;
   heapify(arr, n, largest);
}

最後に、ソートされた配列がmain（）関数に表示されます。これは、次のコードスニペットで確認できます。

Console.Write("\nSorted Array is: ");
for (i = 0; i < n; i++) {
   Console.Write(arr[i] + " ");
}