ヒープソートの基本的なアイデアは、ソートする配列をヒープと呼ばれる特殊なデータ構造に変換することです。ヒープは、完全二分木であり、親ノードが子ノードよりも大きい（または小さい）という特性を持ちます。
まず、与えられた配列をヒープに変換するために、以下の手順を実行します。
- 配列を逆順に走査し、親ノードと子ノードの関係を確認します。
- 親ノードが子ノードよりも小さくない（または大きくない）場合、親ノードと子ノードを交換します。
- すべての親ノードに対して上記の手順を繰り返します。これによって、最大ヒープ（または最小ヒープ）が構築されます。
ヒープが構築されたら、以下の手順でソートを行います。
- 最大ヒープ（または最小ヒープ）のルート要素を取り出し、配列の最後の要素と交換します。
- 配列の最後の要素をソート済みの部分とみなし、ヒープの範囲を狭めます。
- ヒープの範囲内で、再び最大ヒープ（または最小ヒープ）を構築します。
- 1から3の手順を繰り返し、全体の配列がソートされるまで続けます。
以下に、C言語でのヒープソートの実装例を示します。
#include <stdio.h>
// 配列の要素を交換する関数
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 最大ヒープを構築する関数
void heapify(int arr[], int n, int i) {
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) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// ヒープソートを実行する関数
void heapSort(int arr[], int n) {
// 最大ヒープを構築する
for (int i = n / 2 - 1; i >=0; i--) {
heapify(arr, n, i);
}
// ヒープから要素を取り出し、ソートする
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("ソート前の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
heapSort(arr, n);
printf("\nソート後の配列: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}このプログラムは、与えられた配列をヒープソートアルゴリズムを使用して昇順にソートします。上記のコードを実行すると、ソート前の配列とソート後の配列が表示されます。
ヒープソートは一般的に効率的なアルゴリズムですが、最悪の場合の時間計算量はO(n log n)です。また、追加のメモリ領域を使用しないため、インプレースソートアルゴリズムとしても知られています。