平成30年春期午後問8

CEさん  
(No.1)
https://www.fe-siken.com/kakomon/30_haru/pm08.html
30年春ヒープソートに関する問題のプログラム1のswap入れ替え部分の質問になります。
tmp←heap[i]でheapi番目の配列要素の値を入れるまではわかります。
ただ、次のheap[i]←heap[j]ときますがこのjの要素番号は何番になって、
heap[i]に対して入れる配列要素の値をどうして返されるのかが分かりません。
意味合いとしては、子の値が親より大きいから一度tmpにいれて、
親と子の値を入れ替えているのは分かりますがしっくりきません。
どなたかご教授願いませんでしょうか?
2021.02.21 14:06
ミカンボウさん 
(No.2)
アルゴリズムを最初から丁寧に読んでください。
解説にあるデータ例を参考にします。
データが今回は「30,60,15,5,10,20」とします。
副プログラムmakeheapをトレースすると、1回目の繰り返しはk=0なので何も起きません。
2回目の繰り返しで、k=1となり、配列の0番目と1番めが比較され、もう一つの繰り返しに入ります。そして、60>30なので、true分岐に入ります。
そこで、副プログラムswapが出てきます。
swapにここで与えられる引数は(型名は省略します)
「heap[],k,b]
です。
では、中身の数字を詳しく言うと、
「heapという配列の中の、k番目と(この場合は1)、その親(この場合は0)」
となります。
ここまで分かると、swapの中で何が行われているのかが分かるはずです。
swapに与えられた引数は、プログラムの中で
「heap[k],i,j]
となります。つまり、繋げればi=k,J=その親ということになります。
tmp←heap[i](tmpという一時的な変数に配列1番目の要素60を逃がす)
heap[i]←heap[j](配列1番目に30を代入)
heap[j]←tmp(配列0番目にtmpに逃した60を代入)
これでプログラム2つの処理は全て見たことになります。
もしまだわからなければ、質問してください。
2021.02.22 09:34

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。

その他のスレッド


Pagetop