JavaScriptで学ぶアルゴリズム③［ソートアルゴリズム⑷］-ヒップソート

外資系企業でソフトウェアエンジニアをしております、タロイモと言います。今日もよろしくお願いします。

本日はソートアルゴリズムのヒープソートを紹介します。

O(n log n)

以下の図を見て分かるとおり、O(n log n)はアルゴリズムとしてはあまり優れていません。

ただソートアルゴリズムはO(n^2)とO(n log n)しかないため、順番に並んでないバラバラなデータのときは、このO(n log n)アルゴリズムが最速になります。

ヒープソート

ヒープとは、データの中で一番小さい数が一番上に来る木構造のデータ構造のことです。

ヒープソートはこのヒープというデータ構造を利用します。

ヒープは上の例で言えば、一番小さい数が一番上に来ていますが、ヒープソートは一番大きい数を上に持っていきます。

例えば、1, 2, 4, 5, 6, 7, 9, 10, 11, 12（順番はこの通りでない）という数列があったら、

このようにヒープ構造にします。
これを小さい順にソートするために上の大きい数から取り出していきます。

次に二番目に大きい11が一番上に来ます。
ヒープの再構築の順番に関しては割愛します。

これを繰り返し、小さい順番に並び替えていきます。

これがヒープソートです。

ちなみに再構築にn回かかり、計算時間がO(log n)なので、O(n log n)という計算時間になります。log nというのはヒープの高さです。
今回はデータ数が10なので、n = 10になり、log 10 ≒ 3で、ヒープの高さは3になります。（図を見れば分かりますが、、）

ヒープソートをJavaScriptで表すと以下のようになります。
[参考］http://www.nichijou-int.com/sisan/archives/20501788.html

function heap_sort(a) {
 let array_size = a.length;

 //ヒープ構築
 for (let i = parseInt((array_size - 1) / 2); i >= 0; i--) {
   maxInt(a, i, array_size - 1);
 }

 //ヒープソート実行
 //値を昇順に並べる。

 //先頭要素(最大値)を配列の最後に移動
 //最後の要素を無視してヒープを構築
 //配列内で最も小さな値から順に並ぶ
 let temp;
 for (let i = array_size - 1; i > 0; i--) {
   temp = a[0];
   a[0] = a[i];
   a[i] = temp;
   maxInt(a, 0, i - 1);
 }
}

//@param a ソートしたい配列
//@param root 親ノードとなる要素の添字
//@param bottom 最後の要素の添字
function maxInt(a, root, bottom) {
 //子ノードの添字
 let child = 2 * root + 1;

 //親ノードの値を一時保持
 let temp = a[root];

 while (child <= bottom) {
   if (child < bottom && a[child + 1] > a[child]) {
     //二分木のふたつの子ノードから値が大きい子ノードを選択
     child = child + 1;
   }
   if (temp > a[child]) {
     //親ノードの値が子ノードの値より大きい場合はそのまま
     break;
   } else if (temp <= a[child]) {
     //親が子より小さいか等しいときは親と子を入れ替える
     a[parseInt((child - 1) / 2)] = a[child];
     //子ノードの添字を一つ上げるå
     child = 2 * child + 1;
   }
 }
 //親ノードとなる要素に値を入れる
 a[parseInt((child - 1) / 2)] = temp;
}

let array = [2, 1, 7, 8, 3, 9, 4, 6, 5];
heap_sort(array);
console.log(array); //[1, 2, 3, 4, 5, 6, 7, 8, 9]

今回もご精読ありがとうございました。