C++でヒープソートアルゴリズムを使って10個の要素の配列をソートする方法

ヒープソートは、二分ヒープ（バイナリヒープ）と呼ばれるデータ構造に基づいたソートアルゴリズムです。二分ヒープには2種類あります。最大ヒープでは各親ノードの子ノードが親の値以下になり、最小ヒープでは各親ノードの子ノードが親の値以上になるように構成されます。本記事では、最大ヒープを利用したヒープソートをC++で実装し、10個の要素を持つ配列を昇順に並べ替える手順を詳しく解説します。

ヒープソートの手順（具体例）

まず、ソート前の10個の要素からなる元の配列は次の通りです。

この配列に対してmax-heapify操作を適用し、二分最大ヒープを構築します。配列として表現された最大ヒープは以下のようになります。

次に、最大ヒープのルート要素（最大値）を取り出して配列の末尾に配置します。その後、残りの要素に対して再びmax-heapifyを呼び出し、ヒープ構造を維持します。この操作を繰り返すことで、最終的に次のようなソート済み配列が得られます。

C++プログラム例

ヒープソートアルゴリズムを使用して10個の要素の配列をソートする完全なプログラムは以下の通りです。

#include<iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int temp;
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    int temp;
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (int i = n - 1; i >= 0; i--) {
        temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
    int n = 10;
    int i;
    cout<<"Given array is: "<<endl;
    for (i = 0; i < n; i++)
    cout<<arr[i]<<" ";
    cout<<endl;
    heapSort(arr, n);
    printf("\nSorted array is: \n");
    for (i = 0; i < n; ++i)
    cout<<arr[i]<<" ";
}

出力結果

Given array is:
20 7 1 54 10 15 90 23 77 25
Sorted array is:
1 7 10 15 20 23 25 54 77 90

プログラムの詳細解説

heapify()関数 ― 要素をヒープ構造に変換する

上記プログラムでは、heapify()関数が要素をヒープ構造へ変換する役割を担います。この関数は再帰的に動作し、呼び出し時のインデックスiを起点として、その要素を根とする部分木を最大ヒープに構成します。該当するコードは以下の通りです。

void heapify(int arr[], int n, int i) {
    int temp;
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest])
        largest = l;
    if (r < n && arr[r] > arr[largest])
        largest = r;
    if (largest != i) {
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

具体的には、インデックスiの左右の子（それぞれ2*i+1と2*i+2）と比較し、最も大きい要素を特定します。最大値が親自身でない場合は値を交換し、交換先の位置に対して再帰的にheapify()を呼び出すことで、下方向へもヒープ条件を伝播させます。

heapSort()関数 ― 配列をヒープソートで並べ替える

heapSort()関数は、ヒープソートの本体であり、配列の要素を実際に並べ替えます。まず、葉ノード以外のノード（インデックスn/2−1から0まで）に対してheapify()を呼び出し、配列全体を二分最大ヒープへ変換します。この処理は以下のコードで行われます。

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

続いて、forループの各反復においてルート要素（現時点での最大値）を取り出し、配列の末尾に移動します。その後、heapify()を呼び出して残りの要素が最大ヒープの条件を満たすように整えます。この操作をすべての要素に対して繰り返すことで、昇順にソートされた配列が完成します。該当するコードは以下の通りです。

for (int i = n - 1; i >= 0; i--) {
    temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;
    heapify(arr, i, 0);
}

main()関数 ― ソートの実行と結果表示

main()関数では、まず元の配列の内容を画面に出力します。その後、heapSort()関数を呼び出して配列をソートします。該当するコードスニペットは以下の通りです。

cout<<"Given array is: "<<endl;
for (i = 0; i < n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);

最後に、ソート後の配列を出力して処理完了となります。以下にそのコードを示します。

printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";

計算量について

ヒープソートの時間計算量は、最良・平均・最悪のいずれの場合でもO(n log n)であり、入力データの初期状態に依存せず安定した性能を発揮します。また、追加のメモリ領域をほとんど必要としないインプレース（in-place）ソートである点も大きな特徴です。ただし、クイックソートと比べると定数倍が大きく、キャッシュ効率が劣るため、実用上は状況に応じて使い分けられます。