top

ヒープソート


ヒープソートとは?

ヒープソートの考え方は、まず、データをヒープ構造にし、完成したらデータの先頭の値を取り出す。そしてまたヒープ構造を作り・・・という繰り返しである。

ここでヒープ構造とは、簡単に言うと、2分木の各節点にデータを保持し、親のデータが2つの子のデータよりも大きくなるように作られたデータ構造である。

つまり、これから分かることは全てのデータの中で2分木の「根」、すなわちデータの先頭に最大値を持つデータが必ず存在する。という事である。



考え方

配列N[]に次のようなデータが格納されているとする。

4 1 6 2 9 7 3 8

これを2分木で表現すると、

heap1   

上図のようになる。

ヒープソートを行うには、まず、この配列(2分木)をヒープ構造にする必要がある。ヒープ構造の特徴は先にも述べた通り、次のようなものである。


  1. 二分木の根には必ず最大値がくる。
  2. 親子関係、すなわちN[a]・N[2a+1]・N[2a+2]の
    値を比較したとき、必ず親であるN[a]の値が最大となる。


【ヒープ構造】

では次に、実際にこのデータをヒープ構造にしていく。

ヒープ構造にする際の考え方は以下のようなものである。


  1. 配列N[0]〜N[length]に値が格納されている時(すなわちデータの数はlength+1である)、k = (length - 1) / 2 、a = kとする。このN[k]が親ノードとなる。

  2. j = 2 * k + 1とする。つまり、N[j]はN[k]の左側の子である。 もし、N[j + 1]にノードが存在するなら(つまり右側にも子があるなら)、N[k]とN[j]とN[j + 1]の値を比較する。

  3. 葉がない時(k = j または k = j + 1 としてもその下に子がない時)、a = a - 1 、 k = a とし、同様の操作を続ける。


  4. a = 0 の時、同様の操作を行い、終了となる。


文章だけでは理解に苦しむので、図を用いて説明する。

『1』今回の例ではlength = 7 であるので、k = 3 , a = 3 である。

『2』k = 3 より j = 7 と求まる。j = j + 1 には子が存在しないので、N[k] と N[j]の値を比較する。

heap2

この時、N[j]の値が最大であるのでこの2つの値を入れ替える。

『3』k = j = 7 とするが、子が存在しないので、a の値を一つ減らし2とする。同様にk = 2 とする。

『2』k = 2 より j = 5 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。

heap3

この時、N[j] の値が最大であるのでこの2つの値を入れ替える。

『3』k = j = 5 とするが、子が存在しないので、a の値を一つ減らし1とする。同様にk = 1 とする。

『2』k = 1 より j = 3 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。

heap4

この時、N[j + 1] の値が最大であるのでこの2つの値を入れ替える。

『3』k = j + 1 = 4 とするが、子が存在しないので、a の値を一つ減らし0とする。同様にk = 0 とする。

『2』k = 0 より j = 1 と求まる。j = j + 1 に子が存在するので、N[k] と N[j] と N[j + 1] の値を比較する。

heap5

この時、N[j] の値が最大であるのでこの2つの値を入れ替える。

k = j = 1 とし、、また、j = 3 とする。j = j + 1 に子が存在するのでN[k] と N[j] と N[j + 1] の値を比較する。

この時、N[j] の値が最大であるのでこの2つの値を入れ替える。

k = j = 3 とし、、また、j = 7 とする。j = j + 1 には子が存在しないので、N[k] と N[j]の値を比較する。

N[k] の値が最大なので、a の値を1つ減らし、k = a とする。

『4』a の値が負となるので、終了である。

以上でヒープ構造が完成する。図を見てもらえば明らかだが、どの親ノードもその子ノードよりも大きな値を持つことが分かる。




【ヒープソート】

ヒープソートを行うには、ヒープ構造の特徴である「根(配列の先頭、N[0])に必ず最大値が来る」という点を利用する。

この根の部分(配列の先頭)と配列の末尾を入れ替え、配列の末尾を取り除く。残った配列を再びヒープ構造に直す。この1連の操作を繰り返すのがヒープソートである。



では、先程ヒープ構造にした配列Nをヒープソートすると、以下のようになる。

heap6



以下、同様の操作を続けていくことによってヒープソートが完成する。



なお、ヒープソートのアルゴリズムは以下のように記述できる。



    void sort() {					// ヒープソート(昇順)
	for (int i = (length - 2) / 2; i >= 0; i--) {
	    downheap(i, length - 1);
	}
	for (int i = length - 1; i > 0; i--) {
	    swap(0, i);
	    downheap(0, i - 1);
	}
    }

    void downheap(int k, int r) {
	int j, v;
	v = a[k];
	while (true) {
	    j = 2 * k + 1;
	    if (j > r) break;
	    if (j != r) {
		if (a[j + 1] > a[j]) {
		    j = j + 1;
		}
	    }
	    if (v >= a[j]) break;
	    a[k] = a[j];
	    k = j;
	}
	a[k] = v;
    }

    void swap(int i, int j) {				// 要素の交換
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
    }

※プログラム引用

Lecture of Computer Programming I by Hiroshi Ichiji




では実際にアプレットを動かしてみる。

まず数字の書いたボタンをクリックする。

その数字の数だけノードが表示される。

以下は、上に書いた説明に従ってソートすべき2つのノードをドラッグアンドドロップする。

next

back