【C#】HeapSortの実装を絵とコードで整理してみる

今、アルゴリズム図鑑という本を読んで、ヒープソートアルゴリズムを実装してみました。ネット上にあるコードをベースに自分ならこう書くだろうなという考えのもと実装してみました。参考にしたのは下記サイトです。

ufcpp.net

ですが、途中からコードの内容がよくわからなくなってきたので、絵を書きながら確認していきました。忘れないようにメモとして残しておこうと思います。

今回書いたコード

github.com

これをベースに書いていきます。

HeapSort(ヒープソート)

ヒープデータ構造を利用したソートです。今回は降順ヒープにしています。ヒープデータ構造では下記の性質を持ちます。

• 親の要素は子の要素よりも大きい(降順)/小さい(昇順)
• 子は最大で2つ持つ
• 要素は左詰め

今回の問題

今回は、下記配列をヒープを使ってソートしていきます。

int[] array = new int[9] { 5, 9, 3, 1, 2, 8, 4, 7, 6 };

最初にやること

まずは、インプットとなる配列をヒープに格納します。先程の配列をヒープに格納すると下記のようになります。ちなみに、大前提としてヒープデータ構造は配列で表現しています。ヒープデータ構造のどの要素が配列のどの要素に紐付いているのか確認してみてください。

{9,8,6,7,3,2,5,1,4}

ヒープの格納をコードで実装します。

下記の処理で既存の配列をヒープに格納します。まずは呼び出し側の処理。

for (int i = 1; i < array.Length; i++)
{
    MakeHeap(array, i);
}

呼び出される側の処理。

static void MakeHeap(int[] array, int n)
{
    while (n != 0)
    {
        int i = (n - 1) / 2;
        if (array[n].CompareTo(array[i]) > 0) Swap(ref array[n], ref array[i]);
        n = i;
    }
}

n-1番目まではヒープに格納が完了していて、n番目の要素をヒープに追加する処理として書いています。配列のn番目の要素を追加する時に、親になる要素と大きさを比較して、n番目の要素の値の方が親よりも大きければ配置を交換します。ヒープは左詰めの性質をもつので追加する要素が配列の何番目にあるかで、親の要素が一意にきまります(” int i = (n - 1) / 2;”この式の部分)。これを要素数-1回分繰り返すと無事ヒープに格納が終わります。(最初の一つは格納済みの状態から始まるので要素数-1回となる)

次にやること

まずは、ヒープに格納するところで準備が完了です。次は、そのヒープからデータを取り出す必要があります。ヒープはかならず最大の値を取り出すことになります(昇順の場合は最小値)。下記がイメージです。(④書き忘れた・・・)

static int PopHeap(int[] array, int n)
{
    int max = array[0];
    array[0] = array[n];
    for (int i = 0, j; (j = 2 * i + 1) < n;)
    {
        if ((j != n - 1) && (array[j].CompareTo(array[j + 1]) < 0)) j++;
        if (array[i].CompareTo(array[j]) < 0) Swap(ref array[i], ref array[j]);
        i = j;
    }
    return max;
}

②③がこの部分です。maxという変数にarray[0] = 9 を入れてます。

int max = array[0];
array[0] = array[n];

④(ないけど左下の図)を実装しているのがこれです。for文のj = 2 * i + 1は奇数の要素(各子の左側の要素)を表しています。

for (int i = 0, j; (j = 2 * i + 1) < n;)
{
    if ((j != n - 1) && (array[j].CompareTo(array[j + 1]) < 0)) j++;
    if (array[i].CompareTo(array[j]) < 0) Swap(ref array[i], ref array[j]);
    i = j;
}

これを繰り返して一番したの要素まで見ればヒープデータ構造の性質を満たすことができます。