ヒープソートの仕組みとC++実装を解説｜アルゴリズム・計算量・サンプルコード

ヒープソートとは

ヒープソート（Heap Sort）は、「ヒープ」というデータ構造を利用して行うソートアルゴリズムの一つです。ヒープは完全二分木であり、大きく分けて次の2種類があります。

• 最小ヒープ（Min-Heap）： 根（ルート）の要素が常に最小値となる構造
• 最大ヒープ（Max-Heap）： 根の要素が常に最大値となる構造

ヒープソートでは、まずデータ列から最大ヒープを構築します。次に、根にある要素（最大値）を取り出し、配列の末尾の要素を根へ移動させます。この入れ替えによってヒープの性質が崩れるため、配列全体を再びヒープ化（再ヒープ化）します。この「根から削除 → 再ヒープ化」の操作を繰り返すことで、配列全体を昇順に並べ替えることができます。

ヒープソートの計算量

• 時間計算量： O(n log n)
• 空間計算量： O(1)

入力と出力の例

入力:
未ソートのデータ列: 30 8 99 11 24 39
出力:
ソート前の配列: 30 8 99 11 24 39
ソート後の配列: 8 11 24 30 39 99

アルゴリズム

heapify(array, size)

入力 − データの配列と、配列内の全要素数

出力 − 配列の要素から構築された最大ヒープ

Begin
    for i := 1 to size do
        node := i
        par := floor (node / 2)
        while par >= 1 do
            if array[par] < array[node] then
                swap array[par] with array[node]
            node := par
            par := floor (node / 2)
        done
    done
End

heapSort(array, size)

入力 − データの配列と、配列内の全要素数

出力 − ソート済みの配列

Begin
    for i := n to 1 decrease by 1 do
        heapify(array, i)
        swap array[1] with array[i]
    done
End

C++による実装例

#include<iostream>
using namespace std;

void display(int *array, int size) {
    for(int i = 1; i<=size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void heapify(int *array, int n) {
    int i, par, node;
    // 最大ヒープを構築

    for(i = 1; i<= n; i++) {
        node = i; par = (int)node/2;
        while(par >= 1) {
            // 新しいノードが親より大きければ交換
            if(array[par] < array[node])
                swap(array[par], array[node]);
            node = par;
            par = (int)node/2;// 親を更新して確認
        }
    }
}

void heapSort(int *array, int n) {
    int i;

    for(i = n; i>= 1; i--) {
        heapify(array, i);// 毎回ヒープ化する
        swap(array[1], array[i]);// 先頭要素と末尾要素を交換
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n+1]; // 有効なインデックスは i = 1 から開始
    cout << "Enter elements:" << endl;

    for(int i = 1; i<=n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    heapSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 6
Enter elements:
30 8 99 11 24 39
Array before Sorting: 30 8 99 11 24 39
Array after Sorting: 8 11 24 30 39 99

まとめ

ヒープソートは、最悪の場合でも時間計算量がO(n log n)で安定した性能を保証しつつ、追加メモリがほぼ不要（空間計算量 O(1)）という点が大きな強みのソートアルゴリズムです。平均ケースの定数倍ではクイックソートに劣るものの、最悪ケースでも性能が崩れない信頼性の高さから、実務や組み込み分野でも広く活用されています。