回答編集履歴
2
書式の改善
test
CHANGED
|
@@ -242,7 +242,7 @@
|
|
|
242
242
|
|
|
243
243
|
|
|
244
244
|
|
|
245
|
-
### 4.main関数の処理
|
|
245
|
+
### 4. main関数の処理
|
|
246
246
|
|
|
247
247
|
```C++
|
|
248
248
|
|
1
降順を昇順に変更
test
CHANGED
|
@@ -102,7 +102,7 @@
|
|
|
102
102
|
|
|
103
103
|
```
|
|
104
104
|
|
|
105
|
-
ループの条件は「rootよりも子のほうがcostが
|
|
105
|
+
ループ(スワップ)の条件は「rootよりも子のほうがcostが小さい」です。これはwhile文で判断するには条件が複雑なので、`while (true)`とし、whileループ内でrootと子の大小を比較します。そして、rootよりも子のほうが小さい場合はスワップし、rootのほうが小さい場合はbreak文でループを抜けます。また、rootが子を持つかどうかの判断も必要なため、asizeを引数にします。(leaf引数は削除)
|
|
106
106
|
|
|
107
107
|
|
|
108
108
|
|
|
@@ -140,37 +140,37 @@
|
|
|
140
140
|
|
|
141
141
|
{
|
|
142
142
|
|
|
143
|
-
int l
|
|
143
|
+
int smallest; //rootと子ノードのうち最もcostが小さいノード
|
|
144
144
|
|
|
145
145
|
while (true)
|
|
146
146
|
|
|
147
147
|
{
|
|
148
148
|
|
|
149
|
-
l
|
|
149
|
+
smallest = root;
|
|
150
|
-
|
|
150
|
+
|
|
151
|
-
if (left(root) < asize && a[left(root)].cost
|
|
151
|
+
if (left(root) < asize && a[left(root)].cost < a[smallest].cost)
|
|
152
|
-
|
|
152
|
+
|
|
153
|
-
l
|
|
153
|
+
smallest = left(root); //rootが左の子を持ち、かつ左の子がsmallestよりも小さいとき
|
|
154
|
-
|
|
154
|
+
|
|
155
|
-
if (right(root) < asize && a[right(root)].cost
|
|
155
|
+
if (right(root) < asize && a[right(root)].cost < a[smallest].cost)
|
|
156
|
-
|
|
156
|
+
|
|
157
|
-
l
|
|
157
|
+
smallest = right(root); //rootが右の子を持ち、かつ右の子がsmallestよりも小さいとき
|
|
158
|
-
|
|
159
|
-
|
|
160
|
-
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
-
if (l
|
|
161
|
+
if (smallest == root)
|
|
162
|
-
|
|
162
|
+
|
|
163
|
-
break; //rootが最
|
|
163
|
+
break; //rootが最小ならループを抜ける
|
|
164
164
|
|
|
165
165
|
else
|
|
166
166
|
|
|
167
167
|
{
|
|
168
168
|
|
|
169
|
-
//子のほうが
|
|
169
|
+
//子のほうが小さいならスワップする
|
|
170
|
-
|
|
170
|
+
|
|
171
|
-
swap(a, root, l
|
|
171
|
+
swap(a, root, smallest);
|
|
172
|
-
|
|
172
|
+
|
|
173
|
-
root = l
|
|
173
|
+
root = smallest;
|
|
174
174
|
|
|
175
175
|
}
|
|
176
176
|
|
|
@@ -402,25 +402,25 @@
|
|
|
402
402
|
|
|
403
403
|
{
|
|
404
404
|
|
|
405
|
-
int l
|
|
405
|
+
int smallest;
|
|
406
406
|
|
|
407
407
|
while (true)
|
|
408
408
|
|
|
409
409
|
{
|
|
410
410
|
|
|
411
|
-
l
|
|
411
|
+
smallest = root;
|
|
412
|
-
|
|
412
|
+
|
|
413
|
-
if (left(root) < asize && a[left(root)].cost
|
|
413
|
+
if (left(root) < asize && a[left(root)].cost < a[smallest].cost)
|
|
414
|
-
|
|
414
|
+
|
|
415
|
-
l
|
|
415
|
+
smallest = left(root);
|
|
416
|
-
|
|
416
|
+
|
|
417
|
-
if (right(root) < asize && a[right(root)].cost
|
|
417
|
+
if (right(root) < asize && a[right(root)].cost < a[smallest].cost)
|
|
418
|
-
|
|
418
|
+
|
|
419
|
-
l
|
|
419
|
+
smallest = right(root);
|
|
420
|
-
|
|
421
|
-
|
|
422
|
-
|
|
420
|
+
|
|
421
|
+
|
|
422
|
+
|
|
423
|
-
if (l
|
|
423
|
+
if (smallest == root)
|
|
424
424
|
|
|
425
425
|
break;
|
|
426
426
|
|
|
@@ -428,9 +428,9 @@
|
|
|
428
428
|
|
|
429
429
|
{
|
|
430
430
|
|
|
431
|
-
swap(a, root, l
|
|
431
|
+
swap(a, root, smallest);
|
|
432
|
-
|
|
432
|
+
|
|
433
|
-
root = l
|
|
433
|
+
root = smallest;
|
|
434
434
|
|
|
435
435
|
}
|
|
436
436
|
|
|
@@ -538,29 +538,29 @@
|
|
|
538
538
|
|
|
539
539
|
(id/cost)
|
|
540
540
|
|
|
541
|
-
0/
|
|
541
|
+
0/29
|
|
542
|
-
|
|
542
|
+
|
|
543
|
-
1/
|
|
543
|
+
1/87 2/72
|
|
544
|
-
|
|
544
|
+
|
|
545
|
-
3/
|
|
545
|
+
3/52 4/31 5/76 6/1
|
|
546
|
-
|
|
546
|
+
|
|
547
|
-
7/
|
|
547
|
+
7/54 8/38 9/69 10/74 11/100 12/44 13/4 14/30
|
|
548
|
-
|
|
548
|
+
|
|
549
|
-
15/
|
|
549
|
+
15/25 16/63 17/95 18/48 19/74 20/57 21/54 22/83 23/65 24/39 25/22 26/73 27/97 28/2 29/97
|
|
550
550
|
|
|
551
551
|
|
|
552
552
|
|
|
553
553
|
(id/cost)
|
|
554
554
|
|
|
555
|
-
|
|
555
|
+
6/1
|
|
556
|
-
|
|
556
|
+
|
|
557
|
-
2
|
|
557
|
+
15/25 28/2
|
|
558
|
-
|
|
558
|
+
|
|
559
|
-
|
|
559
|
+
8/38 4/31 25/22 13/4
|
|
560
|
-
|
|
560
|
+
|
|
561
|
-
|
|
561
|
+
3/52 18/48 20/57 21/54 24/39 12/44 0/29 14/30
|
|
562
|
-
|
|
562
|
+
|
|
563
|
-
1
|
|
563
|
+
7/54 16/63 17/95 1/87 19/74 9/69 10/74 22/83 23/65 11/100 5/76 26/73 27/97 2/72 29/97
|
|
564
564
|
|
|
565
565
|
|
|
566
566
|
|