ヒープソート実装・詳しい計算量解説

ヒープソート(Heap Sort)

このサイトでのヒープソートの定義は以下の通りです。¹

計算量 $O(N \log N)$

ヒープとは

ヒープソートを理解するためには、まず「二分ヒープ(Binary Heap)」というデータ構造を知る必要があります。

二分ヒープは、以下の性質を持つ二分木です。

• 形状条件: 完全二分木である(葉の段以外は完全に埋まっており、葉の段は左から詰める)
• 順序条件: 親の値は子の値以上である(最大ヒープの場合)

完全二分木は、配列で表現することができます。

配列のインデックスを $0$ から始めるとき、インデックス $i$ のノードについて以下が成り立ちます。

• 親: インデックス $\lfloor (i-1)/2 \rfloor$
• 左の子: インデックス $2i+1$
• 右の子: インデックス $2i+2$

つまり、追加のメモリを使わずに、配列だけで二分ヒープを表現できます。

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

ヒープソートは「二分ヒープ」を利用した効率的なソートアルゴリズムです。大きく分けて 2 つのフェーズで動作します。

1. ヒープ構築フェーズ: 配列全体を最大ヒープに変形する
2. 取り出しフェーズ: 最大値(根)を末尾と交換してヒープサイズを 1 減らし、根からヒープ条件を再構築する操作を繰り返す

これにより、配列の末尾から順に最大値が確定していき、最終的に昇順にソートされた配列が得られます。

sift-down(下方向への再ヒープ化)

ヒープソートの中核となる操作が「sift-down(または heapify-down)」です。

ある節点を根とする部分木がヒープ条件を満たすように、根の値を下に降ろしていく操作です。

1. 左右の子のうち大きい方を選ぶ
2. その子と根を比較して、子の方が大きければ交換する
3. 交換した先(子のあった場所)を新しい根として 1 から繰り返す
4. 葉に到達するか、ヒープ条件を満たしたら終了

ヒープ構築

配列全体を最大ヒープにするには、葉でない最後のノード($\lfloor N/2 \rfloor - 1$ 番目)から順にインデックスを下げながら sift-down を適用します。

葉から作るのではなく、葉でないノードに対してだけ sift-down を行うのがポイントです。葉は単独でヒープ条件を満たしているからです。

最大値の取り出し

ヒープが構築できたら、根(配列の先頭)が最大値です。

1. 根と未ソート部分の末尾を交換する
2. 末尾の最大値はソート確定となるので、ヒープサイズを 1 減らす
3. 新しい根に対して sift-down を行い、ヒープ条件を回復する
4. ヒープサイズが 1 になるまで 1〜3 を繰り返す

実装例

以下に C 言語での実装例を示します。

#include <stdio.h>
 
void siftDown(int *data, int start, int end)
{
    int root = start;
    while (2 * root + 1 <= end)
    {
        int child = 2 * root + 1;
        if (child + 1 <= end && data[child] < data[child + 1])
        {
            child++;
        }
        if (data[root] < data[child])
        {
            int tmp = data[root];
            data[root] = data[child];
            data[child] = tmp;
            root = child;
        }
        else
        {
            return;
        }
    }
}
 
void heapSort(int *data, int n)
{
    // ヒープ構築フェーズ
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        siftDown(data, i, n - 1);
    }
    // 取り出しフェーズ
    for (int end = n - 1; end > 0; end--)
    {
        int tmp = data[0];
        data[0] = data[end];
        data[end] = tmp;
        siftDown(data, 0, end - 1);
    }
}

ヒープソートの計算量

ヒープソートの計算量を、ヒープ構築フェーズと取り出しフェーズに分けて議論します。

データ数 $N$ は $N = 2^k - 1$ と表せるとします(完全二分木の各段が完全に埋まっている場合)。

このとき木の高さは $k - 1 = \log_2(N+1) - 1$ です。

sift-down の計算量

sift-down は根から葉に向かって最大で木の高さぶん降りていく操作です。

高さ $h$ のノードを根とする部分木に対する sift-down の最悪比較回数は $2h$ 回(各段で左右の子の比較と親子の比較で 2 回)以下です。

したがって sift-down 1 回の計算量は $O(\log N)$ です。

ヒープ構築フェーズの計算量

ヒープ構築フェーズでは、葉でない $N/2$ 個のノードに対して sift-down を行います。

単純に考えると $\frac{N}{2} \times O(\log N) = O(N \log N)$ となりますが、実はもっとタイトに評価できます。

高さ $h$ のノードの個数は最大で $\lceil N / 2^{h+1} \rceil$ 個です。

各高さ $h$ のノードに対する sift-down の比較回数は最大で $2h$ 回なので、ヒープ構築フェーズ全体の比較回数は以下のように評価できます。

ここで、無限級数の公式

を用いると、

となります。

したがって、ヒープ構築フェーズの計算量は $O(N)$ です。

取り出しフェーズの計算量

取り出しフェーズでは、$N - 1$ 回の取り出しを行い、それぞれで sift-down(計算量 $O(\log N)$)を呼び出します。

したがって取り出しフェーズの計算量は

となります。

全体の計算量

ヒープソート全体の計算量は

となります。

ヒープソートはマージソートやクイックソートと同じ $O(N \log N)$ ですが、以下のような特徴があります。

• インプレースソート: 追加のメモリをほとんど必要としない(マージソートとの違い)
• 最悪計算量も $O(N \log N)$ で安定: クイックソートのように最悪 $O(N^2)$ になることがない
• 安定ソートではない: 同じ値の要素の相対順序が保たれない場合がある

組み込みやメモリ制約のある環境でも安定して $O(N \log N)$ を保証したいときに、ヒープソートは有力な選択肢になります。

以上がヒープソートの基本的な解説と C 言語での実装、および計算量の議論でした。

関連記事

ソートアルゴリズムを一覧で比較したい方はソートアルゴリズム比較・計算量まとめをご覧ください。

• バブルソート
• 選択ソート
• 挿入ソート
• シェーカーソート
• シェルソート
• マージソート
• クイックソート