質問編集履歴
4
問題箇所の目処
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -9,8 +9,6 @@
|
|
|
9
9
|
11 45 24 18 23 12 34
|
|
10
10
|
|
|
11
11
|
```
|
|
12
|
-
|
|
13
|
-
|
|
14
12
|
|
|
15
13
|
|
|
16
14
|
|
|
@@ -155,3 +153,31 @@
|
|
|
155
153
|
}
|
|
156
154
|
|
|
157
155
|
```
|
|
156
|
+
|
|
157
|
+
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
途中結果
|
|
162
|
+
|
|
163
|
+
```
|
|
164
|
+
|
|
165
|
+
swap(0, 6)
|
|
166
|
+
|
|
167
|
+
34 18 12 45 23 24 11
|
|
168
|
+
|
|
169
|
+
pushdown(0, 5)
|
|
170
|
+
|
|
171
|
+
12 18 34 45 23 24 11
|
|
172
|
+
|
|
173
|
+
12 18 34 45 23 24 11
|
|
174
|
+
|
|
175
|
+
12 18 11 45 23 24 34
|
|
176
|
+
|
|
177
|
+
12 18 11 45 23 24 34
|
|
178
|
+
|
|
179
|
+
```
|
|
180
|
+
|
|
181
|
+
この結果を見た感じ、せっかく最後尾に持って行った11が前array[2]にきている。
|
|
182
|
+
|
|
183
|
+
pushdownの中で子の小さい方を選んでいるので、親34と子(24, 11)だと11が選ばれswap34<->11されているみたいです…
|
3
結果
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -6,7 +6,7 @@
|
|
|
6
6
|
|
|
7
7
|
```
|
|
8
8
|
|
|
9
|
-
1 45
|
|
9
|
+
11 45 24 18 23 12 34
|
|
10
10
|
|
|
11
11
|
```
|
|
12
12
|
|
2
min関数のreturn値、pushdown関数の中のj = iをi = jに
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -34,13 +34,15 @@
|
|
|
34
34
|
|
|
35
35
|
int min(int array[], int i){
|
|
36
36
|
|
|
37
|
-
i
|
|
37
|
+
int i1 = 2*i+1, i2 = 2*i+2;
|
|
38
38
|
|
|
39
|
+
if(array[i1] > array[i2])
|
|
40
|
+
|
|
39
|
-
return
|
|
41
|
+
return i2;
|
|
40
42
|
|
|
41
43
|
else
|
|
42
44
|
|
|
43
|
-
return
|
|
45
|
+
return i1;
|
|
44
46
|
|
|
45
47
|
}
|
|
46
48
|
|
|
@@ -74,7 +76,7 @@
|
|
|
74
76
|
|
|
75
77
|
swap(array, i, j); // 親iとjの内容を変換
|
|
76
78
|
|
|
77
|
-
|
|
79
|
+
i = j; // さらに子孫を調べる
|
|
78
80
|
|
|
79
81
|
} else {
|
|
80
82
|
|
1
コメントを補足
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -30,6 +30,8 @@
|
|
|
30
30
|
|
|
31
31
|
|
|
32
32
|
|
|
33
|
+
// iの子の値の小さい方を返す
|
|
34
|
+
|
|
33
35
|
int min(int array[], int i){
|
|
34
36
|
|
|
35
37
|
if(array[2*i+1] > array[2*i+2])
|
|
@@ -44,6 +46,8 @@
|
|
|
44
46
|
|
|
45
47
|
|
|
46
48
|
|
|
49
|
+
// 入れ替え
|
|
50
|
+
|
|
47
51
|
void swap(int array[], int i, int j){
|
|
48
52
|
|
|
49
53
|
int tmp = array[i];
|
|
@@ -56,23 +60,25 @@
|
|
|
56
60
|
|
|
57
61
|
|
|
58
62
|
|
|
63
|
+
// 反順序性の回復/確保
|
|
64
|
+
|
|
59
65
|
void pushdown(int array[], int first, int last){
|
|
60
66
|
|
|
61
67
|
int i = first;
|
|
62
68
|
|
|
63
69
|
while(i <= (last-1)/2){
|
|
64
70
|
|
|
65
|
-
int j = min(array, i);
|
|
71
|
+
int j = min(array, i); // iの子の値の小さい方
|
|
66
72
|
|
|
67
|
-
if(array[j] < array[i]){
|
|
73
|
+
if(array[j] < array[i]){ // 子 < 親
|
|
68
74
|
|
|
69
|
-
swap(array, i, j);
|
|
75
|
+
swap(array, i, j); // 親iとjの内容を変換
|
|
70
76
|
|
|
71
|
-
j = i;
|
|
77
|
+
j = i; // さらに子孫を調べる
|
|
72
78
|
|
|
73
79
|
} else {
|
|
74
80
|
|
|
75
|
-
return;
|
|
81
|
+
return; // 逆転はないので終了
|
|
76
82
|
|
|
77
83
|
}
|
|
78
84
|
|
|
@@ -82,9 +88,15 @@
|
|
|
82
88
|
|
|
83
89
|
|
|
84
90
|
|
|
91
|
+
// ヒープソート
|
|
92
|
+
|
|
85
93
|
void heapSort(int array[]){
|
|
86
94
|
|
|
87
95
|
int i;
|
|
96
|
+
|
|
97
|
+
// 配列arrayをヒープとみなす
|
|
98
|
+
|
|
99
|
+
// 反順序性を確立し、arrayを完全なヒープに変換する
|
|
88
100
|
|
|
89
101
|
for(i = N/2 -1; i >= 0; i--){
|
|
90
102
|
|
|
@@ -92,17 +104,23 @@
|
|
|
92
104
|
|
|
93
105
|
}
|
|
94
106
|
|
|
107
|
+
// ヒープから最小値を順次取り出し、arrayの後ろへ並べていく
|
|
108
|
+
|
|
95
109
|
for(i = N-1; i >= 1; i--){
|
|
96
110
|
|
|
97
|
-
swap(array, 0, i);
|
|
111
|
+
swap(array, 0, i); // ヒープの先頭から最小値を取り除く
|
|
98
112
|
|
|
99
|
-
pushdown(array, 0, i-1);
|
|
113
|
+
pushdown(array, 0, i-1); // 反順序性を回復する
|
|
100
114
|
|
|
101
115
|
}
|
|
116
|
+
|
|
117
|
+
// 最終的に大きい順に並んだ配列arrayが得られる
|
|
102
118
|
|
|
103
119
|
}
|
|
104
120
|
|
|
105
121
|
|
|
122
|
+
|
|
123
|
+
// 出力
|
|
106
124
|
|
|
107
125
|
void showdata(int array[]){
|
|
108
126
|
|