teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問ヒープソートを行う際、要素に重複があるとダウンヒープがうまくいかない

編集履歴

質問編集履歴

4

2018/05/12 07:17

投稿

wassho1
wassho1

スコア5

test CHANGED
File without changes
test CHANGED
@@ -28,7 +28,7 @@
28
28
 
29
29
  3
30
30
 
31
- 5
31
+ 4
32
32
 
33
33
  $ ./heap
34
34
 

3

タイトルを変更しました

2018/05/12 07:17

投稿

wassho1
wassho1

スコア5

test CHANGED
@@ -1 +1 @@
1
- ヒープソートを行う際、要素に重複があるとうまくダウンヒープがうまくいかない
1
+ ヒープソートを行う際、要素に重複があるとダウンヒープがうまくいかない
test CHANGED
File without changes

2

ソースコードをすべて記載しました

2018/05/12 06:38

投稿

wassho1
wassho1

スコア5

test CHANGED
File without changes
test CHANGED
@@ -102,7 +102,207 @@
102
102
 
103
103
  for(i=0;i<N;i++){
104
104
 
105
+ fscanf(fp, "%d",&Data[i]);
106
+
107
+ }
108
+
109
+ fclose(fp);
110
+
111
+
112
+
113
+ for(i=0;i<N;i++){
114
+
115
+ printf("%d ", Data[i]);
116
+
117
+ }
118
+
105
- fscanf(fp,"%d");
119
+ printf("\n");
120
+
121
+
122
+
123
+ heapsort(Data,N);
124
+
125
+
126
+
127
+ for(i=0;i<N;i++){
128
+
129
+ printf("%d ", Data[i]);
130
+
131
+ }
132
+
133
+ printf("\n");
134
+
135
+
136
+
137
+ return 0;
138
+
139
+ }
140
+
141
+
142
+
143
+ int parent(int i){//親を返す関数
144
+
145
+ int ans;
146
+
147
+ ans = (double)(i-1)/2;
148
+
149
+ return ans;
150
+
151
+ }
152
+
153
+ int left(int i){//左の子を返す関数
154
+
155
+ int ans;
156
+
157
+ ans = 2*i+1;
158
+
159
+ return ans;
160
+
161
+ }
162
+
163
+
164
+
165
+ int right(int i){//右に子を返す関数
166
+
167
+ int ans;
168
+
169
+ ans =2*i+2;
170
+
171
+ return ans;
172
+
173
+ }
174
+
175
+
176
+
177
+ void Upheap_sort(int H[], int i){//一番後ろの要素をheapの性質を満たすように並べ替える関数.
178
+
179
+ int u,tmp;
180
+
181
+ u = i;
182
+
183
+ while(u>0 && H[parent(u)]<H[u]){
184
+
185
+ tmp = H[parent(u)];
186
+
187
+ H[parent(u)] = H[u];
188
+
189
+ H[u] = tmp;
190
+
191
+ u = parent(u);
192
+
193
+ }
194
+
195
+ }
196
+
197
+
198
+
199
+ void Build_Heap(int H[],int n){//heapをつくる関数
200
+
201
+ int i;
202
+
203
+ for(i=1;i<n;i++){
204
+
205
+ Upheap_sort(H,i);
206
+
207
+ }
208
+
209
+ }
210
+
211
+
212
+
213
+ void Downheap_sort(int H[],int n){//根の値をheapの性質にしたがって直す関数
214
+
215
+ int u,l,r,tmp;
216
+
217
+ u=0;
218
+
219
+ l=1;
220
+
221
+ r=2;
222
+
223
+ while(l!=u && r!=u){//l=r=uとなれば終了
224
+
225
+ if(left(u)<=n){//左の子がいるかいないかで場合分け
226
+
227
+ l = left(u);
228
+
229
+ }
230
+
231
+ else{
232
+
233
+ l = u;
234
+
235
+ }
236
+
237
+ if(right(u)<=n){//右も同様
238
+
239
+ r = right(u);
240
+
241
+ }
242
+
243
+ else{
244
+
245
+ r = u;
246
+
247
+ }
248
+
249
+ if(H[l]>H[u] || H[r]>H[u]){//H[l]もしくはH[r]のどちらかの値がH[u]の値を超えていたらこの操作に入る
250
+
251
+ if(H[l]>=H[r]){//H[l]がH[r]以上ならば左の子とH[u]の値を交換
252
+
253
+ tmp = H[u];
254
+
255
+ H[u] = H[l];
256
+
257
+ H[l] = tmp;
258
+
259
+ u = l;
260
+
261
+ }
262
+
263
+ else{
264
+
265
+ tmp = H[u];
266
+
267
+ H[u] = H[r];
268
+
269
+ H[r] = tmp;
270
+
271
+ u = r;
272
+
273
+ }
274
+
275
+ }
276
+
277
+ else{//H[l], H[r]がともにH[u]以下の場合このループをぬけ出す.
278
+
279
+ l = u;
280
+
281
+ r = u;
282
+
283
+ }
284
+
285
+ }
286
+
287
+ }
288
+
289
+
290
+
291
+ void heapsort(int H[],int n){//heapsort関数
292
+
293
+ int i,tmp;
294
+
295
+ Build_Heap(H,n);
296
+
297
+ for(i=1;i<n;i++){
298
+
299
+ tmp = H[n-i];
300
+
301
+ H[n-i] = H[0];
302
+
303
+ H[0] = tmp;
304
+
305
+ Downheap_sort(H,n-i-1);
106
306
 
107
307
  }
108
308
 
@@ -114,14 +314,4 @@
114
314
 
115
315
  ### 試したこと
116
316
 
117
-
118
-
119
- ここに問題に対して試したことを記載してください。
317
+ ヒープをつくることは正常にできました.
120
-
121
-
122
-
123
- ### 補足情報（FW/ツールのバージョンなど）
124
-
125
-
126
-
127
- ここにより詳細な情報を記載してください。

1

質問内容を追加しました

2018/05/12 06:29

投稿

wassho1
wassho1

スコア5

test CHANGED
@@ -1 +1 @@
1
- ヒープソートを行う際、要素に重複があるとうまくダウンヒープできないことについて
1
+ ヒープソートを行う際、要素に重複があるとうまくダウンヒープがうまくいかない
test CHANGED
@@ -1,34 +1,112 @@
1
- ~~c~~### 前提・実現したいこと
1
+ ###　前提・実現したいこと
2
2
 
3
-
4
-
5
- ここに質問の内容を詳しく書いてください。
6
-
7
- （例）PHP(CakePHP)で●●なシステムを作っています。
8
-
9
- ■■な機能を実装中に以下のエラーメッセージが発生しました。
3
+ 配列の要素に重複がある場合でもヒープソートを実現したい.
10
-
11
-
12
4
 
13
5
  ### 発生している問題・エラーメッセージ
14
6
 
15
-
7
+ 配列の要素に重複がある場合, 以下のような結果になります.
16
8
 
17
9
  ```
18
10
 
11
+ $ cat data1.txt
12
+
13
+ 9
14
+
15
+ 4
16
+
17
+ 2
18
+
19
+ 3
20
+
21
+ 4
22
+
23
+ 9
24
+
25
+ 7
26
+
27
+ 5
28
+
29
+ 3
30
+
31
+ 5
32
+
19
- エラーメッセージ
33
+ $ ./heap
34
+
35
+ input filename:data1.txt
36
+
37
+ 4 2 3 4 9 7 5 3 4
38
+
39
+ 2 3 4 4 3 5 4 7 9
20
40
 
21
41
  ```
22
42
 
23
-
43
+ data1.txtの１行目は要素の個数を表しているので関係はございません. ２行目以降がヒープソートを実行したい配列の要素になります.
24
44
 
25
45
  ### 該当のソースコード
26
46
 
27
47
 
28
48
 
29
- ```ここに言語名を入力
49
+ ```c
30
50
 
51
+ #include<stdio.h>
52
+
53
+ #include<stdlib.h>
54
+
55
+ #include<string.h>
56
+
57
+
58
+
59
+ int parent(int i);
60
+
61
+ int left(int i);
62
+
63
+ int right(int i);
64
+
65
+ int right(int i);
66
+
67
+ void Upheap_sort(int H[],int n);
68
+
69
+ void Build_Heap(int H[], int n);
70
+
71
+ void Downheap_sort(int H[], int n);
72
+
73
+ void heapsort(int H[],int n);
74
+
75
+
76
+
77
+ int main(void){
78
+
79
+ int Data[50];/*数値を格納する配列*/
80
+
81
+ int N;/*読み込む要素数*/
82
+
31
- ソースコード
83
+ int i;
84
+
85
+ char fname[128];//読み込むファイルの名前をかくのうする変数
86
+
87
+ FILE *fp;
88
+
89
+
90
+
91
+ printf("input filename:");
92
+
93
+ fgets(fname,sizeof(fname),stdin);//標準入力からファイル名を取得
94
+
95
+ fname[strlen(fname)-1] = '\0';//最後の行改行コードを削除
96
+
97
+ fflush(stdin);//128文字を超えた入力を標準入力から捨てる
98
+
99
+ fp = fopen(fname, "r");//ファイルを読み込みモードで開く
100
+
101
+ fscanf(fp,"%d",&N);
102
+
103
+ for(i=0;i<N;i++){
104
+
105
+ fscanf(fp,"%d");
106
+
107
+ }
108
+
109
+ }
32
110
 
33
111
  ```
34
112