ヒープソートアルゴリズム

ヒープデータ構造を活用したインプレースソートアルゴリズムを学ぼう

O(n log n)

時間計算量（保証）

O(1)

空間計算量

中級

難易度

インプレース

特性

🔧 実行設定

配列:

[64, 34, 25, 12, 22, 11, 90]

要素数:

配列（カンマ区切り、最大10個）

🌳

アルゴリズムを実行してください

左側の設定パネルから条件を設定し、「ヒープソート実行」ボタンを押してください

💻 実装例（JavaScript）

function heapSort(arr) {
    const n = arr.length;
    
    // フェーズ1: 最大ヒープを構築
    buildMaxHeap(arr);
    
    // フェーズ2: 要素を一つずつ取り出してソート
    for (let i = n - 1; i > 0; i--) {
        // ルート（最大値）を現在の末尾と交換
        swap(arr, 0, i);
        
        // ヒープサイズを減らしてヒープ化
        heapify(arr, i, 0);
    }
    
    return arr;
}

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

function heapify(arr, heapSize, rootIndex) {
    let largest = rootIndex;
    const leftChild = 2 * rootIndex + 1;
    const rightChild = 2 * rootIndex + 2;
    
    // 左の子と比較
    if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }
    
    // 右の子と比較
    if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }
    
    // 最大値がルートでない場合、交換して再帰的にヒープ化
    if (largest !== rootIndex) {
        swap(arr, rootIndex, largest);
        heapify(arr, heapSize, largest);
    }
}

function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 使用例
const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = heapSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 34, 64, 90]

🔧 実行設定

アルゴリズムを実行してください

ヒープソートアルゴリズムとは？

💻 実装例（JavaScript）