バニラJavaScriptでヒープソートを実装する方法をわかりやすく解説

ヒープソートとは

ヒープソートは、要素同士を比較しながら並べ替える「比較ベースのソートアルゴリズム」の一つです。選択ソートの改良版と考えることができます。選択ソートと同様に、入力データを「ソート済み領域」と「未ソート領域」に分割し、未ソート領域から目的の要素(最大値または最小値)を取り出してソート済み領域へ移動させる、という処理を繰り返すことで未ソート領域を少しずつ縮小していきます。

ヒープソートの最大の特徴は、二分ヒープ(バイナリヒープ)というデータ構造を利用する点です。ヒープを構築することで最大値(または最小値)を効率的に取り出せるため、平均・最悪どちらのケースでも計算量が O(n log n) と安定した高速なソートを実現できます。

ヒープソートの処理の流れ

1. 配列全体から最大ヒープ(親ノードが子ノード以上の値を持つ木構造)を構築する
2. ヒープの根(最大値)を配列の末尾の要素と交換する
3. ヒープのサイズを1つ減らし、根を起点にヒープを再構築する
4. 未ソート部分がなくなるまで上記の手順を繰り返す

実装コード

バニラJavaScriptでヒープソートを実装したコードは以下のとおりです。

const constructHeap = (arr, ind) => {
  let left = 2 * ind + 1;
  let right = 2 * ind + 2;
  let max = ind;
  if (left < len && arr[left] > arr[max]) {
    max = left;
  }
  if (right < len && arr[right] > arr[max]) {
    max = right;
  }
  if (max != ind) {
    swap(arr, ind, max);
    constructHeap(arr, max);
  }
}

function swap(arr, index_A, index_B) {
  let temp = arr[index_A];
  arr[index_A] = arr[index_B];
  arr[index_B] = temp;
}

function heapSort(arr) {
  len = arr.length;
  for (let ind = Math.floor(len / 2); ind >= 0; ind -= 1) {
    constructHeap(arr, ind);
  }
  for (ind = arr.length - 1; ind > 0; ind--) {
    swap(arr, 0, ind);
    len--;
    constructHeap(arr, 0);
  }
}

const arr = [3, 0, 2, 5, -1, 4, 1];
heapSort(arr);
console.log(arr);
var len;

実行結果

コンソールには以下のように出力されます。

[
    -1, 0, 1, 2,
    3, 4, 5
]

コードのポイント

• constructHeap関数:指定したインデックスを根とする部分木がヒープの条件(親 ≥ 子)を満たすよう、再帰的に要素を入れ替えて調整します。
• swap関数:配列内の2つの要素を入れ替えるためのヘルパー関数です。
• heapSort関数:まず配列の中央から先頭に向かってヒープを構築し、その後、末尾から順に最大値を確定させながらソートを進めます。

まとめ

ヒープソートは追加のメモリをほとんど必要としないインプレースソートであり、最悪ケースでも O(n log n) の性能を保証する実用的なアルゴリズムです。JavaScriptの標準ライブラリに依存せず、ソートの内部動作を理解したい場合の学習題材としても最適です。