Java
11.public class HeapSort { 22. // 配列の要素a[i1]とa[i2]を交換 33. static void swap(int[] a, int i1, int i2) { 44. int t = a[i1]; 55. a[i1] = a[i2]; 66. a[i2] = t; 77. } 88. 99. // a[left]-a[right]をヒープ化 1010. static void downHeap(int[] a, int left, int right) { 1111. int temp = a[left]; // 根 1212. int child; // 大きいほうの子 1313. int parent; // 親 1414. 1515. for (parent = left; parent < (right + 1) / 2; parent = child) { 1616. int cl = parent * 2 + 1; // 左の子 1717. int cr = cl + 1; // 右の子 1818. if (cr <= right && a[cr] > a[cl]) { 1919. // cr <=rightの条件より右の子は存在しなくてもエラーにならない 2020. child = cr; 2121. } else { 2222. child = cl; 2323. } 2424. if (temp >= a[child]) { 2525. break; 2626. } 2727. a[parent] = a[child]; 2828. } 2929. a[parent] = temp; 3030. } 3131. 3232. // ヒープソート 3333. static void heapSort(int[] a) { 3434. int n = a.length; 3535. for (int i = (n - 1) / 2; i >= 0; i--) { // a[i]-a[n-1]をヒープ化 3636. downHeap(a, i, n - 1); 3737. } 3838. for (int i = n - 1; i > 0; i--) { 3939. swap(a, 0, i); // 最大要素と未ソート部末尾要素を交換 4040. downHeap(a, 0, i - 1); // a[0]-a[i - 1]をヒープ化 4141. } 4242. } 4343.}
こちらの本で書かれているヒープソートのプログラムについて質問です。
35行目のfor文のiの初期条件である(n - 1) / 2と
15行目のfor文の条件式ででてくる(right + 1) / 2が何を表しているのかが分かりません。
テキストによるとメソッドdownHeapは配列をヒープ化していくときに、最下流の右側から始めて左側へと進んでいき、そのレベルが終了したら一つ上流側へと移動しながら、部分木をヒープ化していくと書いてあります。
上記の2つのfor文の中の(n - 1) / 2と (right + 1 ) / 2によって配列の適切な位置からヒープ化を始められるというのはnに具体的な値を代入していくことで確認できたのですが、それぞれ2つの値が何を表していて、それらを(n - 1) / 2と (right + 1) / 2から求められるかが分からないので、教えて頂きたいです。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/06/11 02:22