ヒープソート完全解説 - 二分ヒープで理解するソートアルゴリズム

初心者でも理解できるヒープソートの仕組みを詳しく解説。二分ヒープの構造から実装まで、具体的なコード例とともに学習できます。

アルゴリズム学習で「なんとなく」から脱却したいあなたへ

「ソートアルゴリズムは理解しているつもりだけど、ヒープソートだけは仕組みがよく分からない」「面接でアルゴリズムを聞かれたときに自信を持って答えられない」そんな悩みを抱えていませんか？

Fivenine Designでは、これまで20年以上にわたってWeb開発を手がける中で、多くのエンジニアの方々とお話する機会がありました。その中で気づいたのは、基本的なアルゴリズムの理解が不十分なまま実装に入ってしまい、後になって性能問題に直面するケースが非常に多いということです。

特にヒープソートは、常にO(n log n)の時間計算量が保証されるという優秀な特性を持ちながら、二分ヒープの概念が理解しにくいため敬遠されがちなアルゴリズムです。しかし、この記事を読み終える頃には、ヒープソートの仕組みを完全に理解し、自信を持って実装できるようになるはずです。

なぜヒープソートは「難しい」と感じられるのか

抽象的な概念が多い

ヒープソートが理解しにくい最大の理由は、「ヒープ」という抽象的なデータ構造を理解する必要があることです。配列を直接操作するバブルソートや選択ソートと異なり、ヒープソートでは配列を「完全二分木」として捉え、親子関係を意識しながら操作を行います。

あるクライアントのエンジニアの方からは「配列なのになぜ木構造として扱うのか最初は全く理解できなかった」という声をいただきました。確かに、この概念の転換が最初の壁となることが多いのです。

複数の操作が組み合わさる

ヒープソートは以下の複数の操作を組み合わせて実現されます：

ヒープ化（Heapify）: 配列を二分ヒープに変換する
要素の抽出: 最大（または最小）要素を取り出す
ヒープの再構築: 抽出後にヒープ性を回復する

これらの操作がどう連携するかを理解するまでが困難なのです。

実用性が見えにくい

「なぜヒープソートを学ぶ必要があるのか」という疑問も、学習意欲を削ぐ要因の一つです。実際には、ヒープソートは以下のような場面で威力を発揮します：

メモリ使用量を抑えたい場面（インプレースソート）
最悪時間計算量を保証したい場面
優先度付きキューの実装

二分ヒープの構造を理解する

完全二分木としての表現

ヒープソートの核心は「二分ヒープ」というデータ構造にあります。二分ヒープは、以下の性質を満たす完全二分木です：

形状性: 完全二分木である（左から順番に埋まっている）
ヒープ性: 親ノードは子ノードより大きい（最大ヒープの場合）

配列インデックスと親子関係には以下の規則があります：

親のインデックス: (i - 1) / 2
左の子のインデックス: 2 * i + 1
右の子のインデックス: 2 * i + 2

Heapify操作の仕組み

Heapify操作は、ヒープ性を満たさないノードから開始して、適切な位置まで要素を "沈める" 操作です。

function heapify(arr, n, i) {
    let largest = i; // 親ノードを最大と仮定
    let left = 2 * i + 1; // 左の子
    let right = 2 * i + 2; // 右の子
    
    // 左の子が親より大きい場合
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 右の子が現在の最大値より大きい場合
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 最大値が親でない場合、交換して再帰的にheapify
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

def heapify(arr, n, i):
    largest = i  # 親ノードを最大と仮定
    left = 2 * i + 1  # 左の子
    right = 2 * i + 2  # 右の子
    
    # 左の子が親より大きい場合
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 右の子が現在の最大値より大きい場合
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 最大値が親でない場合、交換して再帰的にheapify
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

ヒープソートの完全実装

ステップ1: 初期ヒープの構築

まず、与えられた配列を最大ヒープに変換します。最後の非葉ノード（(n//2) - 1）から開始して、順次heapify操作を適用します。

ステップ2: ソート処理

ヒープから最大要素（ルート）を取り出し、配列の末尾に配置します。その後、ヒープサイズを1減らして再度heapifyを実行します。

function heapSort(arr) {
    const n = arr.length;
    
    // ステップ1: 最大ヒープを構築
    // 最後の非葉ノードから開始して逆順にheapify
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // ステップ2: 要素を一つずつ取り出してソート
    for (let i = n - 1; i > 0; i--) {
        // ルート（最大値）を現在の末尾と交換
        [arr[0], arr[i]] = [arr[i], arr[0]];
        
        // ヒープサイズを減らして再度heapify
        heapify(arr, i, 0);
    }
    
    return arr;
}

// 使用例
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("ソート前:", numbers);
heapSort(numbers);
console.log("ソート後:", numbers);

def heap_sort(arr):
    n = len(arr)
    
    # ステップ1: 最大ヒープを構築
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # ステップ2: 要素を一つずつ取り出してソート
    for i in range(n - 1, 0, -1):
        # ルート（最大値）を現在の末尾と交換
        arr[0], arr[i] = arr[i], arr[0]
        
        # ヒープサイズを減らして再度heapify
        heapify(arr, i, 0)
    
    return arr

# 使用例
numbers = [64, 34, 25, 12, 22, 11, 90]
print("ソート前:", numbers)
heap_sort(numbers)
print("ソート後:", numbers)

処理の流れを可視化

flowchart TD
    A["配列を受け取る"] --> B["初期ヒープ構築"]
    B --> C["最後の非葉ノードから
heapify実行"]
    C --> D["最大ヒープ完成"]
    D --> E["ルート（最大値）を
配列末尾と交換"]
    E --> F["ヒープサイズを1減らす"]
    F --> G["ルートからheapify実行"]
    G --> H{"ヒープサイズ > 1?"}
    H -->|Yes| E
    H -->|No| I["ソート完了"]

O(n log n)が保証される理由

ヒープ構築の時間計算量

初期ヒープの構築には O(n) の時間がかかります。これは直感に反するかもしれませんが、以下の理由によります：

葉ノード（n/2個）: 0回の比較
高さ1のノード（n/4個）: 最大1回の比較
高さ2のノード（n/8個）: 最大2回の比較

数学的に計算すると、総比較回数は O(n) に収束します。

ソート処理の時間計算量

ソート処理では：

(n-1)回のループ
各ループでheapify操作（O(log n)）

結果として O(n log n) の時間計算量になります。

最悪計算量が保証される意味

他の一般的なソートアルゴリズムとの比較：

クイックソート: 平均O(n log n)、最悪O(n²)
マージソート: 常にO(n log n)だが、O(n)の追加メモリが必要
ヒープソート: 常にO(n log n)かつインプレース

この特性により、ヒープソートはリアルタイム処理や組み込みシステムなど、性能の予測可能性が重要な場面で重宝されます。

よくある実装ミスと対処法

ミス1: インデックス計算の間違い

よくある間違い:

// 間違った親子関係の計算
let parent = i / 2; // Math.floorを忘れる
let left = 2 * i; // +1を忘れる
let right = 2 * i + 1; // +2ではなく+1にしてしまう

正しい実装:

let parent = Math.floor((i - 1) / 2);
let left = 2 * i + 1;
let right = 2 * i + 2;

実際にFivenine Designでコードレビューを行った際、このインデックス計算のミスは非常に頻繁に見られます。特にゼロベースインデックスでの計算に慣れていない場合に起こりやすい間違いです。

ミス2: 境界条件の処理不備

問題となるケース:

配列サイズが1の場合
左の子のみ存在する場合
heapifyの範囲外アクセス

対処法:

function heapify(arr, n, i) {
    // 境界チェックを最初に実行
    if (i >= n) return;
    
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    
    // 配列の範囲内かどうかを必ずチェック
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

ミス3: ヒープ構築の開始位置

間違った開始位置:

// 全てのノードからheapifyしてしまう（非効率）
for (let i = n - 1; i >= 0; i--) {
    heapify(arr, n, i);
}

正しい開始位置:

// 最後の非葉ノードから開始
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
}

葉ノードはすでにヒープ性を満たしているため、非葉ノードのみをheapifyすることで効率化が図れます。

ミス4: 再帰の深度制限

大きな配列では再帰呼び出しがスタックオーバーフローを引き起こす可能性があります。本番環境では反復版を使用することを推奨します：

function heapifyIterative(arr, n, i) {
    while (i < n) {
        let largest = i;
        let left = 2 * i + 1;
        let right = 2 * i + 2;
        
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest !== i) {
            [arr[i], arr[largest]] = [arr[largest], arr[i]];
            i = largest; // 次の位置に移動
        } else {
            break; // ヒープ性が満たされた
        }
    }
}

実践的な応用例

優先度付きキューの実装

ヒープソートの理解は、優先度付きキューの実装に直結します：

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    // 要素を挿入（優先度の高い順）
    enqueue(item, priority) {
        const node = { item, priority };
        this.heap.push(node);
        this.bubbleUp();
    }
    
    // 最高優先度の要素を取り出し
    dequeue() {
        if (this.heap.length === 0) return null;
        
        const max = this.heap[0];
        const end = this.heap.pop();
        
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown();
        }
        
        return max.item;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        const element = this.heap[idx];
        
        while (idx > 0) {
            let parentIdx = Math.floor((idx - 1) / 2);
            let parent = this.heap[parentIdx];
            
            if (element.priority <= parent.priority) break;
            
            this.heap[parentIdx] = element;
            this.heap[idx] = parent;
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        const length = this.heap.length;
        const element = this.heap[0];
        
        while (true) {
            let leftChildIdx = 2 * idx + 1;
            let rightChildIdx = 2 * idx + 2;
            let leftChild, rightChild;
            let swap = null;
            
            if (leftChildIdx < length) {
                leftChild = this.heap[leftChildIdx];
                if (leftChild.priority > element.priority) {
                    swap = leftChildIdx;
                }
            }
            
            if (rightChildIdx < length) {
                rightChild = this.heap[rightChildIdx];
                if (
                    (swap === null && rightChild.priority > element.priority) ||
                    (swap !== null && rightChild.priority > leftChild.priority)
                ) {
                    swap = rightChildIdx;
                }
            }
            
            if (swap === null) break;
            
            this.heap[idx] = this.heap[swap];
            this.heap[swap] = element;
            idx = swap;
        }
    }
}

無料相談受付中

お気軽にご相談ください（初回無料）

詳しく見る

まとめと次のステップ

ヒープソートは一見複雑に見えますが、以下の要素を段階的に理解することで確実にマスターできます：

二分ヒープの概念: 配列を完全二分木として捉える
親子関係の計算: インデックスベースの関係性
Heapify操作: 要素を適切な位置に "沈める"
全体のフロー: ヒープ構築 → ソート処理

実際のプロジェクトでヒープソートを活用するためには、以下の点を意識してください：

適用場面の判断:

メモリ使用量を抑えたい場合
最悪時性能の保証が必要な場合
優先度付きキューが必要な場合

実装時のポイント:

インデックス計算のミスに注意
大きなデータセットでは反復版を使用
境界条件の処理を忘れずに

Fivenine Designでは、こうしたアルゴリズムの理解を基盤として、高性能なWebアプリケーションの開発をサポートしています。Laravel、WordPress、Next.jsを使った開発において、適切なデータ構造とアルゴリズムの選択は、ユーザー体験の向上に直結します。

アルゴリズムの学習や実装でお困りの際は、ぜひお気軽にご相談ください。経験豊富なエンジニアチームが、理論から実装まで丁寧にサポートいたします。

二分ヒープの親子関係式を覚える

heapify操作の動作を手順通りに確認

実際にコードを写経して動作確認

小さなデータセットで手動トレース

境界条件のテストケースを作成

優先度付きキューの実装に挑戦

他のソートアルゴリズムとの性能比較