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()メソッドの処理

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()メソッド：ヒープの構築

heapSort()関数は、まず与えられた要素をヒープ構造に変換します。これはforループを使い、ヒープ内のすべての非葉ノード（子を持つ要素）に対してheapify()関数を呼び出すことで実現されます。該当するコード部分は以下のとおりです。

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

heapSort()メソッド：最大値の取り出し

ヒープが構築された後、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()メソッドの処理

heapify()関数は、要素を必要な順序に並べ替えることでヒープ構造を作り上げます。この処理はインデックスiの位置にある要素を起点として開始され、その要素がheapify()関数におけるルートとして扱われます。具体的には、左右の子ノードと値を比較し、最も大きい値を持つノードを特定して親と入れ替えます。入れ替えが発生した場合は、再帰的に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] + " ");
}

以上がC#によるヒープソートの実装例です。ヒープソートの計算量はO(n log n)であり、最悪ケースでも安定したパフォーマンスを発揮する点が特徴です。データ構造の理解を深めるためにも、ぜひ実際にコードを動かしてみてください。