ヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも小さくなるように作られたデータ構造です。すべてのデータの中で、木の根のデータがもっとも小さいことが保障されますから、最小値データを取り出すことや、データの追加が最悪でも log(N) 時間で行えるという、優れた特徴があります。

ヒープソートの基本的な考え方は、与えられたデータを順にヒープ構造に追加して行き、すべてのデータを追加し終わったら根から取り出すと言うものです。

ヒープ構造は、もっとも小さいデータが常に根にあることが特徴です。したがって、すべてのデータをヒープに追加してから、根から順に取り出せば、小さい順にデータを取り出すことが可能です。ただし、データの追加や取り出しのときは、ヒープ構造が壊れないように注意しなければなりません。

ヒープにデータを追加するときは、まず木構造の最後に追加します。このままではヒープ構造の条件を満たさないので、親と比較して子のほうが小さければ入れ替えます。この操作を根にたどり着くか、または親の方が小さくなるまで繰り返します。この操作には、最悪、log(N) 時間を要します。

ヒープから最小のデータを取り出す場合は、その根のデータを取り出せば OK です。しかし、これだけでは根がなくなってヒープ構造が壊れてしまいます。そこで、ヒープの最後のデータを根に移動させます。さらに、ヒープ構造の条件を満たすために、子の小さい方のデータと比較して親の方が大きければ、入れ替えます。これを最後まで繰り返すには、最悪でも log(N) の時間を要します。

Java で書いたヒープソートのアルゴリズムを以下に示します。

【アルゴリズム4】 ヒープソート

public int[] heap; // データの配列 public int num; // 現在の要素数 int target; // 現在の着目ライン /* * 挿入 */ public void insert(int a){ heap[num++]=a; int i=num,j=i/2; while(i>1 && heap[i-1]<heap[j-1]){ int t=heap[i-1]; heap[i-1]=heap[j-1]; heap[j-1]=t; i=j; j=i/2; } } /* * 先頭の要素を取り除き、返す */ public int deletemin(){ int r=heap[0]; heap[0]=heap[--num]; int i=1,j=i*2; while(j<=num){ if(j+1<=num && heap[j-1]>heap[j]) j++; if(heap[i-1]>heap[j-1]){ int t=heap[i-1]; heap[i-1]=heap[j-1]; heap[j-1]=t; } i=j; j=i*2; } return r; } /* * ソート */ public void sort(int[] a){ // 必要なヒープ用配列を確保します heap=new int[a.length]; num=0; // ヒープに要素を追加します for(target=0;target<a.length;target++) insert(a[target]); // ヒープから取り出しながら配列に格納します。 for(target=0;num>0;target++) a[target]=deletemin(); }

Java には標準でヒープ構造クラスはありません。そこで、配列を使用したヒープ構造を、以下のメンバ、メソッドを使って作成しています。

heap	ヒープ構造を保持する配列です。
num	現在、ヒープ構造に保持されているデータ数です。
insert(d)	ヒープ構造にデータ d を追加します。追加後も、ヒープ構造が正しく保たれます。
deletemin()	ヒープから先頭のデータを取り出します。取り出した後も、ヒープ構造が正しく保たれます。

ヒープソートを行うメソッド sort() では、まず、与えられたデータ配列 a[ ] の要素数を格納できるヒープ構造を作成しています。次に、メソッド insert() を使って、そのヒープにデータを追加します。データの追加はばらばらの順番で構いません。最後に、メソッド deleetemin() を使ってヒープの根から次々にデータを取り出して、配列 a[ ] に格納しています。

ヒープソートを可視化して行うアプレットを、下に示します。

"Start" ボタンを押すと、並べ替えが開始されます。

まず始めに、青い線が上から順番に下に移動します。これは、青い線のデータをヒープに追加していることを意味しています。同時に、右側にその時点でのヒープ構造が●で表示されます。青色の濃さは、そのデータの大きさを表します。濃い青ほど、大きな数値が格納されています。○は、そのとき追加されたデータが、ヒープ構造のどこに格納されたかを示しています。ヒープ構造の条件を満たすためにデータの入れ替えが行われた場合は、その過程も表示されます。

すべてのデータをヒープに格納し終わったら、次に、ヒープの根から順番にデータが取り出されます。今度は赤い線がうえから順番に移動し、それに伴ってデータが並べ変わっていきます。このとき、右側のヒープ構造からはデータが取り出され、●が減っていきます。さらに、ヒープ構造の条件を満たすためにデータの入れ替えが行われる過程も○で表示されます。

このアプレットの動作を見ると、ヒープソートアルゴリズムにおいて、データがヒープに追加され、その都度、ヒープがどのように更新されていくか、また、データがヒープから取り出される際に、ヒープがどのように更新されていくかがわかります。

ヒープにデータを追加する場合は、値の小さなデータを追加する場合ほど、データの入れ替えが多く発生して、時間がかかります。また、データを取り出す際は、最後のデータを根に持ってきてから入れ替えを行うため、通常、データを追加する場合よりもデータの入れ替えが多く発生することもわかります。

大きさ N のヒープ構造にデータを追加する、あるいは最小のデータを取り出す作業には、log(N) の時間を要します。N 個のデータを並べ替える場合、データの追加と取り出しを N 回ずつ行う必要がありますので、ヒープソートに要する時間は 2 N log(N) と考えられそうですが、本当でしょうか？

ここで気になるのは、ヒープの大きさはデータの追加・削除によって変化すると言うことです。つまり、並べ替えたいデータの個数が N だからと言って、ヒープ構造の大きさはいつも N であるわけではありません。最初は大きさ 0 で、データを追加する毎に 1 ずつ増えます。大きさが N のヒープに対してデータの追加・削除が log(N) の時間を要するわけですから、追加と削除に要する時間は、

[ log(1) + log(2) + log(3) + … + log(N-1) + log(N) ] x 2

であるはずです。この値は、N を連続であるとして log(x) の 1 から N までの積分として Mathematica で計算すると、

[ (1 - N + N ln(N) )/ln(2) ] x 2

となります。ここで ln(x) は自然対数（底が e ）です。

この値は、定数と N の1次の項を無視すれば 2 N log(N) となりますから、最初に単純に考えた値は、あながち的外れでもなかったわけです。

以上より、ヒープソートのオーダーは O( N log(N) ) ということになります。現実に要する時間は、これよりも若干（ -N の分だけ）短くなるはずです。

← prev | next →