ヒープソートとは

常に最大値(最小値)を取り出すことができるデータ構造があれば、それをソートアルゴリズムに援用できます。 その考えのもと、ヒープソート とは 二分ヒープ と呼ばれるデータ構造を用いてソートを行うアルゴリズムです。

二分ヒープと呼ばれるデータ構造は、二分木を使って作られるデータ構造で、各ノードの値は常に子ノードの値より大きいか等しくなるように配置されます。つまり二分ヒープのルートノードの値は最大値となります。

よって、「ヒープへの追加(UpHeap)」と「ヒープからルートの削除(DownHeap)」についての処理ができれば、ヒープソートを実装できます。

ヒープソートは 不安定 な 内部 ソートです。平均計算量・最悪計算量ともに O(n log n) のため安定して高速で動作します。ただし、なんだかんだクイックソートのほうが速いようです。

ヒープソートのシミュレーション

背景色が黄色のタイミングで比較が実行されています。ツリー形状で表示させて実行すると、徐々にヒープが出来上がっていきます。緑色のタイミングでヒープ木が完成しています。

アルゴリズムの解説

  1. データを取り出し、ヒープに追加(up-heap)します。すべてのデータをヒープに追加するまで繰り返します。
  2. ルートデータを取り出します(down-heap)。ソート済データに取り出したデータを追加します。全データ繰り返してソートが完了します。

ヒープ構造はデータ自体の並びのみで表現できる(ポインタなどを持つ必要がない)という利点を活かし、元のデータ領域をそのまま使うことで内部ソートとして実装できます。

配列をヒープ構造のデータとして表現すると、n番目の要素の親要素のインデックスは (n - 1) / 2 となります。同じく子要素(左)のインデックスは 2n + 1 で求まります。

ヒープへの追加(up-heap)

すでに存在するヒープへデータを追加するには、up-heap と呼ばれる処理を行います。具体的には以下のアルゴリズムに従います。

  1. ヒープの最下層(配列の場合はヒープデータの直後)へデータを追加(up-heap)します。
  2. 追加されたデータの親データと比較し、順序が正しければ処理完了です。
  3. 比較結果が正しくなければ、親データと交換して、停止するまで2.を繰り返します。

ルートの削除(down-heap)

ヒープからルートデータを整合性を保った状態で取り出すには、down-heap と呼ばれる処理を行います。具体的には以下のアルゴリズムに従います。これは up-heap と反対の処理のイメージです。

  1. ルートデータを取り出し再構成(down-heap)します、ヒープ最下層のデータと交換します。
  2. ルートデータを子データと比較し、正しい順序であれば処理完了です。
  3. 比較結果が正しくなければ、子データと交換して、停止するまで2.を繰り返します。

サンプルコード

C#

public static void HeapSort<T>(T[] array) where T : IComparable<T>
{
    int i = 0;
    while (i < array.Length)
    {
        UpHeap(array, i++);
    }
    while (--i > 0)
    {
        // ヒープの最大値を末端へ移動
        Swap(ref array[0], ref array[i]);
        // ヒープを再構成
        DownHeap(array, i - 1);
    }
}

public static void UpHeap<T>(T[] array, int n) where T : IComparable<T>
{
    while (n != 0)
    {
        // ary[n]の親要素のインデックス
        int parent = (n - 1) / 2;
        if (array[n].CompareTo(array[parent]) > 0)
        {
            // 交換後のインデックスを保持
            Swap(ref array[n], ref array[parent]);
            n = parent;
        }
        else
        {
            break;
        }
    }
}

public static void DownHeap<T>(T[] array, int n) where T : IComparable<T>
{
    if (n == 0) return;
    int parent = 0;
    while (true)
    {
        int child = 2 * parent + 1; // ary[n]の子要素
        if (child > n) break;
        if ((child < n) && array[child].CompareTo(array[child + 1]) < 0)
        {
            child++;
        }
        if (array[parent].CompareTo(array[child]) < 0) // 子要素より小さい場合スワップ
        {
            Swap(ref array[parent], ref array[child]);
            parent = child; // 交換後のインデックスを保持
        }
        else
        {
            break;
        }
    }
}

public static void Swap<T>(ref T a, ref T b)
{
    var tmp = a;
    a = b;
    b = tmp;
}