Internet Explorerよりも速くソートできたよ：コーディングに役立つ！ アルゴリズムの基本（5）（3/4 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

[山下寛人，オイシックス株式会社]

ヒープを配列で実装する

　さて、ヒープは完全二分木なので配列で実装することができます。ルートノードを配列のインデックス1とし、以降左上から順にインデックス2、3、……としていきます。

　このとき、親ノード・子ノードのインデックスは簡単に計算することができます。あるノードのインデックスをiとすると、

親ノード	i / 2
左の子ノード	i * 2
右の子ノード	i * 2 + 1

となります。

ヒープからソート結果を得る

　では、ヒープからソート結果を得るにはどうしたらよいでしょうか。ヒープではルートノードが最大であることが分かっているので、まずルートノードを取り出します。

　ルートノードを除外した状態でヒープを再構築します。再びルートノードが最大になるのでルートノードを取り出します。これを最後まで繰り返すと大きい順に値が取得できるのでソートできたことになります。

　実際には配列で実装するのでルートノードを取り出したときに末尾のノードと交換します。末尾のノード（配列の要素）はヒープの対象から外し、ルートノードに対して再構築を掛けます。

　例を挙げて説明します。ルートノード9と末尾のノード3を交換します。

　末尾の要素をヒープの対象から外します。

　ルートノードの3を基準にヒープを再構築します。

以後、同様に最後まで繰り返します。

ヒープソートの実装

　解説が長くなりましたがいよいよソースコードの実装です。こちらもマージソート同様、複雑ではありますが、さほどソースは長くありません。再帰を活用しています。

　前のソースコード37行目にある「末尾7」というコメント行の次に以下のコードを追加してください。

<hr/>
ヒープソート<br/>
<span id="heap"></span>
<script type="text/javascript">
Array.prototype.heapSort = function(compare) {
  this.unshift("");
  var middle = Math.floor(this.length / 2);
  for (var i = middle; 1 <= i; i--) {
    this.heapDown(compare, i, this.length - 1);
  }
 
  for (var i = this.length - 1; 1 <= i; i--) {
    this.swap(1, i);
    this.heapDown(compare, 1, i - 1);
    this.display();
  }
  this.shift();
}
 
Array.prototype.heapDown = function(compare, targetIndex, len) {
  var leftChildIndex = targetIndex * 2;
  var rightChildIndex = leftChildIndex + 1;
  var largestIndex;
  if ((leftChildIndex <= len)&&
    (compare(this[leftChildIndex], this[targetIndex]) > 0)) { 
    largestIndex = leftChildIndex;
  } else {
    largestIndex = targetIndex;
  }
  if ((rightChildIndex <= len) &&
    (compare(this[rightChildIndex], this[largestIndex]) > 0)) {
    largestIndex = rightChildIndex;
  } 
  if (targetIndex != largestIndex) {
    this.swap(targetIndex, largestIndex);
    this.heapDown(compare, largestIndex, len);
  }
}
var heap = arrayForDisplay.clone();
heap.view_id = "heap";
heap.display();
heap.heapSort(compare);
var heapForTime = arrayForTime.clone();
func = function() { heapForTime.heapSort(compare); }
time(func, "ヒープソート", "heap");
</script><!-- 末尾8 -->

　プログラムを解説します。

5〜18行目

ヒープソート本体です。heapDownメソッドは指定のノードからヒープを再構築するメソッドです。

6行目

配列のインデックスは0から始まりますが、1から始めるようにするために先頭に空の要素を追加しています。

7〜9行目

最初にヒープを構築します。末端のノードは除外してもよいため、配列の長さの半分を求め、そこから1に向かってループしながら再構築していきます。

12〜16行目

ヒープからルートノードを取り出しながらソートしていきます。

17行目

6行目で追加した空の要素を削除します。

20〜38行目

ヒープの再構築を行うメソッドです。lenは配列の中で対象にする部分までの長さです。末尾からヒープの対象から外していくため引数で指定します。

24〜33行目

左右の子ノードと比較します。計算したインデックスが配列の長さを超えたり対象の部分の範囲を超えたりする可能性があるのでifの中でチェックしています。

34〜37行目

対象のインデックスが最大でなかった場合はノードの値を交換し、交換後のノードを基準に再度ヒープを再構築していきます。

　では実行してみましょう。実行時間はマージソートと同程度かやや遅いくらいだったと思います。残念です。