Javaでのヒープソートのプログラムについて質問です

Question

1.public class HeapSort {
2.	// 配列の要素a[i1]とa[i2]を交換
3.	static void swap(int[] a, int i1, int i2) {
4.		int t = a[i1];
5.		a[i1] = a[i2];
6.		a[i2] = t;
7.	}
8.
9.	// a[left]-a[right]をヒープ化
10.	static void downHeap(int[] a, int left, int right) {
11.		int temp = a[left]; // 根
12.		int child; // 大きいほうの子
13.		int parent; // 親
14.
15.		for (parent = left; parent < (right + 1) / 2; parent = child) {
16.			int cl = parent * 2 + 1; // 左の子
17.			int cr = cl + 1; // 右の子
18.			if (cr <= right && a[cr] > a[cl]) {
19.				// cr <=rightの条件より右の子は存在しなくてもエラーにならない
20.				child = cr;
21.			} else {
22.				child = cl;
23.			}
24.			if (temp >= a[child]) {
25.				break;
26.			}
27.			a[parent] = a[child];
28.		}
29.		a[parent] = temp;
30.	}
31.
32.	// ヒープソート
33.	static void heapSort(int[] a) {
34.		int n = a.length;
35.		for (int i = (n - 1) / 2; i >= 0; i--) { // a[i]-a[n-1]をヒープ化
36.			downHeap(a, i, n - 1);
37.		}
38.		for (int i = n - 1; i > 0; i--) {
39.			swap(a, 0, i); // 最大要素と未ソート部末尾要素を交換
40.			downHeap(a, 0, i - 1); // a[0]-a[i - 1]をヒープ化
41.		}
42.	}
43.}

こちらの本で書かれているヒープソートのプログラムについて質問です。
35行目のfor文のiの初期条件である(n - 1) / 2と
15行目のfor文の条件式ででてくる(right + 1) / 2が何を表しているのかが分かりません。
テキストによるとメソッドdownHeapは配列をヒープ化していくときに、最下流の右側から始めて左側へと進んでいき、そのレベルが終了したら一つ上流側へと移動しながら、部分木をヒープ化していくと書いてあります。
上記の２つのfor文の中の(n - 1) / 2と (right + 1 ) / 2によって配列の適切な位置からヒープ化を始められるというのはnに具体的な値を代入していくことで確認できたのですが、それぞれ２つの値が何を表していて、それらを(n - 1) / 2と (right + 1) / 2から求められるかが分からないので、教えて頂きたいです。

Answer 1

まず、おそらく34行目は

34.        int n = a.length - 1;

の間違いです。

ヒープソートは下手に文章で説明するよりも図的に理解したほうがいいです。→ヒープソート

35行目のfor文のiの初期条件である(n - 1) / 2

これは配列最後の要素の親のインデックスに当たります。epistemeさんの言う通り、この番号以降の要素は子を持ちません。ここからさかのぼって順次ヒープ構造にしていくということになります。

15行目のfor文の条件式ででてくる(right + 1) / 2

これはヒープ構造にしようとしている範囲内で、子を持たない最初の要素のインデックスを意味します。ヒープ構造にする基準となる親がそこを超えたら、ヒープ構造化完了ということになります。

「なぜ出てくるか」に関して一応数学的な説明を加えることはできますが、参考リンクの図の番号(配列インデックスの番号)の法則性を眺めて理解できればそれで十分です。

Comments

[DAISUKE0549]

回答ありがとうございました。
(n - 1) / 2と(right + 1) / 2が表しているものが理解することが出来ました。
ご指摘頂いたプログラミングのミスですが、おそらくは
34行目の　int n = a.lengthは正しく
35行目を　for (int i = (n - 1) / 2; i >= 0; i--)とするのではなく、
for(int i = (n - 2) / 2; i >= 0 ; i--)とするのが正しいのかと思います。
要素数nが偶数の場合　(n - 1) / 2は配列最後の要素の親のインデックスを表しますが、
nが奇数場合は子を持たない最初のインデックスを表していました。
「なぜ出てくるときは」もう少し自分で考えてみようと思います。
おそらくですが、配列の要素数nと2分木の段数kとした時に、2^(k-1) <= n <= 2^k - 1ということが関係しているのではないかと今のところ思っています。

Answer 2

35行目のfor文のiの初期条件である(n - 1) / 2と 

15行目のfor文の条件式ででてくる(right + 1) / 2が何を表しているのかが分かりません。

(n-1)/2以降の要素は子を持たない(のでそこまで降りれば十分)ってことです。

Comments

[DAISUKE0549]

回答ありがとうございました。(n-1)/2が表す意味を理解すことが出来ました。