Heap Sort

Q: ヒープソートの時間計算量は?

ヒープソートは最良・平均・最悪のいずれのケースでも `O(n log n)` です。ヒープの構築は `O(n)` で、`n` 回の取り出しのそれぞれが `O(log n)` かかります。追加領域は `O(1)` です。

Q: ヒープソートはいつ使うべきですか?

追加メモリが `O(1)` だけで保証された `O(n log n)` の最悪ケースが必要なときにヒープソートを使いましょう。マージソートの `O(n)` バッファなしにクイックソートの `O(n²)` の危険を避けられますが、その代償として安定性とキャッシュ性能を犠牲にします。

Q: ヒープソートとクイックソートの違いは?

どちらもその場でソートしますが、クイックソートには `O(n²)` の最悪ケースがある一方、ヒープソートは `O(n log n)` を保証します。実際にはクイックソートの方がキャッシュ局所性が良く交換も少ないため通常は速く、ヒープソートは主に最悪ケースの上界を保証しなければならないときに選ばれます。

最終更新 2026年7月1日

ヒープソートは配列を二分ヒープとして扱います。まず max-heap を構築し、最大の要素が根（インデックス 0）に来るようにします。次に、根を未整列の最後の要素と繰り返し交換して最大値をその場に固定し、新しい根を下方向にふるい落としてヒープ条件を回復します。上の再生ボタンを押すと、ヒープの構築と取り出しの様子を見られます。

ヒープソートはマージソートと同様に O(n log n) の時間を保証しますが、追加領域は O(1) だけでその場（in-place）でソートします。安定ではなく、クイックソートよりキャッシュ効率が悪くなりがちなので、保証された上界と一定メモリの両方が重要な場合によく選ばれます。

時間計算量と空間計算量

ケース	計算量	備考
最良ケース	O(n log n)	構築 + n 回の取り出し
平均ケース	O(n log n)	ランダムな順序
最悪ケース	O(n log n)	保証される
空間	O(1)	その場
安定	いいえ	ふるい落としが等しい要素を並べ替える

ステップごと

ステップ	何が起きるか
1	配列から max-heap を構築する（最後の親からふるい落とす）。
2	根（最大値）をヒープの最後の要素と交換する。
3	ヒープを1つ縮める - その最後の位置はこれで整列済み。
4	新しい根を下方向にふるい落として max-heap 条件を回復する。
5	ヒープの要素が1つになるまで繰り返す。

具体例

[3, 1, 6, 5, 2, 4] のソート。バー | は縮小するヒープと整列済みの末尾の境界を示します:

パス	配列	操作
ヒープ構築	`[6, 5, 4, 1, 2, 3]`	最後の親からふるい落として max-heap を構築する。`6` が根に来る。
1	`[5, 3, 4, 1, 2 \| 6]`	根 `6` を最後の位置と交換し、ヒープを縮めて `3` をふるい落とす。
2	`[4, 3, 2, 1 \| 5, 6]`	根 `5` を取り出し、`2` をふるい落として `4` を根に上げる。
3	`[3, 1, 2 \| 4, 5, 6]`	根 `4` を取り出し、`1` をふるい落として `3` を根に上げる。
4	`[2, 1 \| 3, 4, 5, 6]`	根 `3` を取り出す。`2` はすでにヒープ条件を満たしている。
5	`[1 \| 2, 3, 4, 5, 6]`	根 `2` を取り出す。残りは1要素なので配列は整列済み。

ヒープソートを使うべき場面

使うべき場面	避けるべき場面
`O(n²)` の危険なしに保証された `O(n log n)` の最悪ケースが必要なとき。	等しいキーの順序を保つ安定ソートが必要なとき。
メモリが限られているとき - 追加領域は `O(1)` だけでその場でソートする。	キャッシュ性能が重要でデータがメモリに収まるとき - クイックソートの方が通常速い。
すでにデータ上でヒープ（例: 優先度付きキュー）を保持しているとき。	比較回数を最小にしたいとき - マージソートやクイックソートは実際にはより少なく比較することが多い。
信頼できない入力がクイックソートの最悪ケースを引き起こしうるが、ランダム化できないとき。	データがほぼ整列済みのとき - 挿入ソートがほぼ線形時間で動作する。

Heap Sortのコード

Python, JavaScript, Java, C++, Cによるクリーンで実行可能なHeap Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。

PythonでのHeap SortのコードPython
1def heap_sort(a):2    n = len(a)3    # Build a max-heap, deepest parent first4    for i in range(n // 2 - 1, -1, -1):5        sift_down(a, i, n)6    # Repeatedly move the max to the end and shrink the heap7    for end in range(n - 1, 0, -1):8        a[0], a[end] = a[end], a[0]9        sift_down(a, 0, end)10    return a11
12
13def sift_down(a, i, size):14    while True:15        largest = i16        left, right = 2 * i + 1, 2 * i + 217        if left < size and a[left] > a[largest]:18            largest = left19        if right < size and a[right] > a[largest]:20            largest = right21        if largest == i:22            return23        a[i], a[largest] = a[largest], a[i]24        i = largest25
26
27nums = [12, 11, 13, 5, 6, 7]28print("Before:", nums)29heap_sort(nums)30print("After: ", nums)
このコードをPythonプレイグラウンドで実行

JavaScriptでのHeap SortのコードJavaScript
1function heapSort(a) {2    const n = a.length;3    // Build a max-heap, then repeatedly move the max to the end4    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) siftDown(a, i, n);5    for (let end = n - 1; end > 0; end--) {6        [a[0], a[end]] = [a[end], a[0]];7        siftDown(a, 0, end);8    }9    return a;10}11
12function siftDown(a, i, size) {13    while (true) {14        const left = 2 * i + 1;15        const right = 2 * i + 2;16        let largest = i;17        if (left < size && a[left] > a[largest]) largest = left;18        if (right < size && a[right] > a[largest]) largest = right;19        if (largest === i) return;20        [a[i], a[largest]] = [a[largest], a[i]];21        i = largest;22    }23}24
25const data = [5, 2, 9, 1, 7, 3];26console.log("Before:", data);27console.log("Sorted:", heapSort([...data]));
このコードをJavaScriptプレイグラウンドで実行

JavaでのHeap SortのコードJava
1import java.util.Arrays;2
3public class Main {4    static void heapSort(int[] arr) {5        int n = arr.length;6        // Build a max-heap, deepest parent first7        for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n);8        // Repeatedly move the max to the end and shrink the heap9        for (int end = n - 1; end > 0; end--) {10            swap(arr, 0, end);11            siftDown(arr, 0, end);12        }13    }14
15    static void siftDown(int[] arr, int i, int size) {16        while (true) {17            int largest = i, l = 2 * i + 1, r = 2 * i + 2;18            if (l < size && arr[l] > arr[largest]) largest = l;19            if (r < size && arr[r] > arr[largest]) largest = r;20            if (largest == i) return;21            swap(arr, i, largest);22            i = largest;23        }24    }25
26    static void swap(int[] arr, int a, int b) {27        int tmp = arr[a];28        arr[a] = arr[b];29        arr[b] = tmp;30    }31
32    public static void main(String[] args) {33        int[] arr = {12, 11, 13, 5, 6, 7};34        System.out.println("Before: " + Arrays.toString(arr));35        heapSort(arr);36        System.out.println("After:  " + Arrays.toString(arr));37    }38}
このコードをJavaプレイグラウンドで実行

C++でのHeap SortのコードC++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void siftDown(std::vector<int>& a, int n, int i) {11    while (true) {12        int largest = i, l = 2 * i + 1, r = 2 * i + 2;13        if (l < n && a[l] > a[largest]) largest = l;14        if (r < n && a[r] > a[largest]) largest = r;15        if (largest == i) return;16        std::swap(a[i], a[largest]);17        i = largest;18    }19}20
21void heapSort(std::vector<int>& a) {22    int n = static_cast<int>(a.size());23    // Build a max-heap in place24    for (int i = n / 2 - 1; i >= 0; --i) siftDown(a, n, i);25    // Repeatedly move the max to the end and shrink the heap26    for (int end = n - 1; end > 0; --end) {27        std::swap(a[0], a[end]);28        siftDown(a, end, 0);29    }30}31
32int main() {33    std::vector<int> data = {12, 11, 13, 5, 6, 7};34    std::cout << "Before: ";35    printVec(data);36    heapSort(data);37    std::cout << "After:  ";38    printVec(data);39    return 0;40}
このコードをC++プレイグラウンドで実行

CでのHeap SortのコードC
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void siftDown(int a[], int n, int i) {9    while (1) {10        int largest = i, l = 2 * i + 1, r = 2 * i + 2;11        if (l < n && a[l] > a[largest]) largest = l;12        if (r < n && a[r] > a[largest]) largest = r;13        if (largest == i) return;14        int tmp = a[i];15        a[i] = a[largest];16        a[largest] = tmp;17        i = largest;18    }19}20
21void heapSort(int a[], int n) {22    // Build a max-heap in place23    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);24    // Repeatedly move the max to the end and shrink the heap25    for (int end = n - 1; end > 0; end--) {26        int tmp = a[0];27        a[0] = a[end];28        a[end] = tmp;29        siftDown(a, end, 0);30    }31}32
33int main(void) {34    int data[] = {12, 11, 13, 5, 6, 7};35    int n = sizeof(data) / sizeof(data[0]);36    printf("Before: ");37    printArr(data, n);38    heapSort(data, n);39    printf("After:  ");40    printArr(data, n);41    return 0;42}
このコードをCプレイグラウンドで実行

ヒープソートに関するよくある質問

ヒープソートの時間計算量は?

ヒープソートは最良・平均・最悪のいずれのケースでも O(n log n) です。ヒープの構築は O(n) で、n 回の取り出しのそれぞれが O(log n) かかります。追加領域は O(1) です。

ヒープソートは安定ですか?

いいえ。ふるい落とし操作は等しい要素を互いに追い越すことがあるため、ヒープソートは等しいキーの相対順序を保ちません。

ヒープソートはいつ使うべきですか?

追加メモリが O(1) だけで保証された O(n log n) の最悪ケースが必要なときにヒープソートを使いましょう。マージソートの O(n) バッファなしにクイックソートの O(n²) の危険を避けられますが、その代償として安定性とキャッシュ性能を犠牲にします。

ヒープソートとクイックソートの違いは?

どちらもその場でソートしますが、クイックソートには O(n²) の最悪ケースがある一方、ヒープソートは O(n log n) を保証します。実際にはクイックソートの方がキャッシュ局所性が良く交換も少ないため通常は速く、ヒープソートは主に最悪ケースの上界を保証しなければならないときに選ばれます。

ヒープソートは優先度付きキューとどう関係しますか?

二分ヒープは優先度付きキューの標準的な実装であり、ヒープソートは本質的にそのキューから最大値を繰り返し取り出すことです。データをすでにヒープで保持しているなら、要素を1つずつ取り出すだけで整列済みの順序が無償で得られます。

ヒープソートには max-heap と min-heap のどちらが必要ですか?

その場で昇順にソートするには max-heap を使います。各パスで最大の要素が末尾に交換され、整列済みの末尾が右から伸びていきます。min-heap はその場で降順を生成し、別の配列に取り出せば昇順になります。