基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

P282のヒープのトレースするあたりに混乱してしまいトレースできません。
教えてください。
要素番号  1 2 3  4  5
値       10 8 4  1  7
これの10と7を入れ替えたいのですが、
if(right<=bottom)and(list[max]<=list[right])
    7       7             1           5
max←right  これで入れ替えになったのかが分かりません
  5    5

そもそも論rightは要素番号3の4じゃないの？

要素番号と要素の値を混同しているような気がします。

>if(right<=bottom)

これは配列の範囲外アクセスを防ぐための記述だと思うので、bottomは5な気がします。

>max←right  これで入れ替えになったのかが分かりません

これだけでは入れ替えてはいないと思います。探索範囲の最大値の要素の要素番号を変数maxに代入する処理ですかね。

>そもそも論rightは要素番号3の4じゃないの？

parent = 1の場合はright = 3で、list[right] = 4だと思います。このifのブロックがwhileのブロックの中にあってwhileブロックの中でparentやrightの値を更新していないでしょうか。

#基本的なデータ構造の質問であれば、変数の説明などを書いて頂ければ書籍を持っていなくても回答できる可能性が高いと思います。

PG
整数型配列heap(整数型の配列：list 整数型：root,整数型  bottom)
整数型left←root*2
整数型left←root*2+1
整数型max

if(left<bottom)and(list[left]>list{root})
max←left
else
max←right
endif

if((right<=bottom)and(list[right]>list[max])
max←right
if(max≠root)
list[root]とlist[max]を入れ替える
list←heap(list,max,bottom)
endif
return list

以上です

right←root×2+1
は間違えました

right←root×2+1
は間違えました

初期状態がNo.1の
>要素番号  1 2 3  4  5
>値       10 8 4  1  7

でよろしいでしょうか？

heapは再帰関数ですかね？heapに最初に与える引数はなんでしょうか。プログラムのendifが１つ足りない気がします。

heapsort ( 10 8 4 1 7)
>要素番号  1 2 3  4  5"
">値       10 8 4  1  7"

G
整数型配列heap(整数型の配列：list 整数型：root,整数型  bottom)
整数型left←root*2
整数型left←root*2+1
整数型max

if(left<bottom)and(list[left]>list{root})
max←left
else
max←right
endif

if((right<=bottom)and(list[right]>list[max])
max←right
endif

if(max≠root)
list[root]とlist[max]を入れ替える
list←heap(list,max,bottom)
endif
return list

お願いいたします。

heapsortとheapは別の関数ですか？

だとしたら

>これの10と7を入れ替えたい

これは関数heapsortの処理だと思いますよ。

＞heapsortとheapは別の関数ですか？

すみません別です

{10,8,4,1,7}は親>=子の関係が成り立っています。

10と7を入れ替えて
{7,8,4,1,10}
先頭と入れ替えて末尾に来た10はヒープ木から切り離して考えます。

{7,8,4,1}をヒープ化します。
{7,8,4,1}→{8,7,4,1}
8と1を入れ替えて
{1,7,4,8}
末尾の8はヒープ木から切り離す。

{1,7,4}をヒープ化します。
{1,7,4}→{7,1,4}
7と4を入れ替えて
{4,1,7}
末尾の7はヒープ木から切り離す。

{4,1}をヒープ化します。（ここはすでにヒープになっている）
4と1を入れ替えて
{1,4}
末尾の4はヒープ木から切り離す。

これでソートが終了し、1,4,7,8,10と昇順ソートできますね。

この投稿は投稿者により削除されました。(2023.08.27 19:55)

12の投稿はheapsortですね。
それはそれで分かるのですが。

if(left<bottom)and(list[left]>list{root})
max←left
else
max←right
endif

if((right<=bottom)and(list[right]>list[max])
max←right
endif

if(max≠root)
list[root]とlist[max]を入れ替える
list←heap(list,max,bottom)
endif
return list 

このPGを見た時に値がどうなるのか読めないんです。
そこからなんです。すみません

PGを1つ1つ読まないとわからないんです。
色々値が混乱して値の流れが分かりません。ごめんなさい

このPGの下に値入れていただけないですか。一行一行開けていきますので
本当に分からないのでごめんなさい。私も悩んでます

if(left<bottom)and(list[left]>list{root})

max←left

else

max←right

endif

if((right<=bottom)and(list[right]>list[max])

max←right

endif

if(max≠root)

list[root]とlist[max]を入れ替える

list←heap(list,max,bottom)

endif

return list

heapはヒープを再構築する関数だと思います。

list = {7,8,4,1,10}
で
heap(list,1,4)を実行すると、

left = 2
right = 3

left = 2,bottom=4で条件式がtrueなので
max←left
max=2

right=3,bottom=4でright<=bottomはtrue
list[right] = 4,list[max]=8なのでlist[right]>list[max]はfalseなのでendifまで飛ぶ

max=2,root=1なのでmax≠rootはtrue
list[root]とlist[max]を入れ替えて
list = {8,7,4,1,10}

heap(list,2,4)を実行（続

ありがとうございます。
しっかり追いかけます

この投稿は投稿者により削除されました。(2023.08.27 23:14)

この投稿は投稿者により削除されました。(2023.08.27 23:14)

私の勘違いだったら申し訳ないのですが、プログラムが間違っているかもしれないです。

この部分

left < bottomがfalseだとmaxにrightが代入されるのが怪しい気がします。

該当部分のプログラムを変えてみたので、読み変えてみるといいかもしれません。
詳しく調べられてないので間違ってるかもです。明日また時間とります。

正直元の
は何をやっているか分かりません。maxが配列の範囲外の要素番号で更新されうるので、list[max]で配列の範囲外にアクセスしてしまいます。


ならば意味は分かります。
他の方の意見も聞きたいです。

この投稿は投稿者により削除されました。(2023.08.28 22:03)

list = {1,7,4,8,10}
heap(list,2,4)を実行する

left=2
right=3
max=1
bottom=2


if(left<=bottom)and(list[left]>list[root]) 
     2    2           （2） 7 （1） 1
max←left      成立したのでendifまで飛ぶ
2     2
------------------------------------------
else

max←right


endif

if((right<=bottom)and(list[right]>list[max])  不成立 endifまで飛ぶ
      3      2            （3）4    （1）7
max←right

endif

if(max≠root)
    2    1
list[root]とlist[max]を入れ替える
      1            7
list←heap(list,max,bottom)

endif

return list

list{7,1,4,8,10}

heapsortで入れ替え
list[4,1,7,8,10]

ということですね。ありがとうございます。

>list = {1,7,4,8,10}
>heap(list,2,4)を実行する

これはどこから来たのですか？

まきさん

No.23はheap(list,1,2）で呼び出した結果としてはlist{7,1,4,8,10}であっている気がしますが・・・

それとは別に
No.1での質問部分とNo.23のトレース結果も違う気がしますし、No.23の何が知りたいのか？とか、○○の部分が不明確とかの、質問ポイントを提示してあげないと答える側も何を書いてあげれば良いのかがわからないと思います。

IPAで公開された問題（ドットコム掲載の問題）で質問されたほうが良いかと。

とりあえず。
No,4, No.8, No.14, No.16 で次のコードが繰り返し登場していますけれど。
★１★２の箇所は、その参考書に本当にそう書いてあるんですか？
また、本当にそう書いてある場合、出版社のホームページなどに正誤表が公開されたりなどしていないんですか。

ちなみに★１の行を、質問者はNo.24では次のように修正していますよね。

>jjon-comさん

ネットに正誤表は出ているんですが、該当ページに関しては記載がなかったですね。ただ正誤表には30個ほどの間違いがあったので、間違っていてもおかしくはないと思います。

ちなみに。
★１の行は 質問者がNo.24で修正した行が正しく、
★２は max←root が正しいのであれば、
プログラムの意味はこうなると思います。

--------
//部分木の節(root)、その左側の子(left)と右側の子(right)、
//という３者の中から最大値を見つけ、親＞子 の関係にする。

//左側の子が存在するなら、左側の子と部分木の節を比較する。
if(left<=bottom)and(list[left]>list[root])
max←left //左側の子が暫定最大値
else
max←root //部分木の節が暫定最大値
endif

//右側の子が存在するなら、右側の子と暫定最大値を比較する。
if((right<=bottom)and(list[right]>list[max])
max←right //右側の子が最大値
endif

//最大値が左側の子または右側の子であったなら
if(max≠root)
list[root]とlist[max]を入れ替える

//交換が発生したなら、左側の子または右側の子を
//新たな部分木の節(root)として、親＞子 の関係を作り出す。
list←heap(list,max,bottom)
endif
return list

No.30のコードは、No.22で まーぼ さんが
> ならば意味は分かります。
と提示したコードと同じ動きです。念のため。

データ構造に関するプログラムはまず、データ構造の理解を深めてからだと思います。

・二分木の節がランダムに並べられているとき、どのようにヒープ化するか。

・二分木の先頭とその子以外が親>=子の関係を満たしているときどのようにヒープ化するか。

この２つは答えられますか。

この２つを理解していないとプログラムを読んでもよく分からないと思います。どのような処理をすればいいのか理解すれば格段に理解しやすくなると思います。

みなさんありがとうございました。
私はただちゃんと理解できるかここでトレースを真似てみて出来ているのか見てほしかったんです。
色々と参考書を読んで見ましたが、この重点対策で自信をつけようとトライしてます。私も理解出来ないんで苦しいのは一緒です。

まーぼさんからの2つの質問はすみません答えられないのでまだ理解出来ないんだと思います。

素直に本に書いてあってもどういう風に理解できないです。説明お願い致します

ところで参考書に載っていたプログラムはjjon-comさんが提示したプログラムで合っていたのでしょうか？

ちなみにNo.17の私の投稿

>list = {8,7,4,1,10}

>heap(list,2,4)を実行（続

とあるので、この続きからは
list{8,7,4,1,10}
でheap(list,2,4)をトレースすることになりますよ。これは要素番号2の節が根で、最後の要素番号が4の二分木が「親>=子の関係」であるかを調べています。listの1～4番目を切り出すと、{8,7,4,1}となり、これはすでにヒープになっているのですが、プログラムはまだ「親>=子の関係を満たしている二分木」とは分かっていないです。

キーワード TXTAF0016 でGoogle検索すると，あるPDFがヒットします。

ヒープという二分木を完成させたら，後は，このPDFの3～4ページの動きで
大きな値から順に決定できる（ヒープソートが進んでいく）
というイメージはできていらっしゃるのでしたっけ？

とりあえず整理して返答します


>まーぼさん
list = {1,7,4,8,10}
>heap(list,2,4)を実行する

これはどこから来たのですか？

重点対策P287の⑤の入れ替え完了のとこからです。

＞jjon-comさん

ヒープという二分木を完成させたら，後は，このPDFの3～4ページの動きで
大きな値から順に決定できる（ヒープソートが進んでいく）
というイメージはできていらっしゃるのでしたっけ？

①1[80](根)と8[20]を交換して80が格納される
②1[20]と2[70]を交換して1[70] 2[20]になる     
③次は2[20]と4[50]と交換  これは親＞子に基づくもの
④次は1[70]と7[40]と交換  
⑤1[80](根)と8[20]を交換して70が格納される
⑥というように根に取り出す値もって来て最後に一番大きい子に根を配置して値を取り出すという動作。

私の理解しているイメージはこういった感じです

この投稿は投稿者により削除されました。(2023.08.29 21:46)

>電タックさん
配慮が足らなくてすみません

>まーぼさん
ところで参考書に載っていたプログラムはjjon-comさんが提示したプログラムで合っていたのでしょうか？

整数型の配列 heap（整数型の配列list,整数型:root,整数型bottom）

整数型:left←root*2
整数型:right←root*2+1
整数型 max

if(leftがbottom以下)and(list[left]がlist[root]より大きい)

max←left

else

max←right

endif

if((rightがbottom以下)and(list[right]がlist[max]より大きい)

max←right

endif

if(maxとrootが等しくない)

list[root]とlist[max]を入れ替える

list←heap(list,max,bottom)

endif

return list

整数型の配列heap_sort(整数型の配列:list)
for(iをlistの要素数から1まで1ずつ減らす)
list←heap(□)

endfor

return list

プログラムを全部書きました。これでいいですか？

まきさん

書籍側の問題でまともにトレースしてもおかしな結果になる可能性もあるので不安になるのは仕方ないです。

ここでやり取りすと結構時間がかかるなーと思っていたのでお互いのためにも端的なポイントで質問したほうがと思ったぐらいです。

ちなみにトレースをする上でNo.24みたいに変数を紙に書き出して変化をどんどん下や右方向に書き足していくのは（消すのが面倒だから）実践的で良い方法だと思いました。
left、right、max
２、＿３、＿＿１
＿＿＿＿＿＿＿２

合格目指して頑張ってください！

まきさん

No.39の
else
max←right

jjon-comさんの(No.30)
else
max←root
の誤植だと思うのでコレでトレースしたほうがいいです。

念の為確認ですが、

if(leftがbottom以下)and(list[left]がlist[root]より大きい)

max←left

else

max←right 

endif

が参考書に載っていたのですよね。
 
max←rootではなく。

間違えました。
max←root
です。すみません

長い間ありがとうございました。
問題自体に不備があるんですね。やっていても気づきませんでした。トレース自体はこれでいいと分かっただけでも嬉しいです。不安でも少しずつでも慣れていくしかありません。
こういった問題ができるようになれば旧試験のヒープの問題に再度チャレンジします。ご指導ありがとうございました。

とりあえずはある節に対して、その節自身と、左の子、右の子の内の3つの値の中で一番大きい数字を持つ節の要素番号を取得したいわけです。これは選択ソート（基本選択法）の考え方でできると思います。

ただ全ての節が子を持つわけではないので、(leftがbottom以下)や(rightがbottom以下)などの条件式が必要になります。

(leftがbottom以下)や(rightがbottom以下)
→ヒープの範囲外ではないことの条件

（list[left]がlist[root]より大きい）や（list[right]がlist[max]より大きい）
→大小比較のための条件式

と分けて考えると分かりやすいかも知れません。

“工業大学生ももやまのうさぎ塾”の”うさぎでもわかるヒープアルゴリズム”というサイトが私は分かりやすいと思います。

念の為ですが、、、、
この書籍に不備が多いのは事実ですが、
質問されている問題に不備は無いと思います。
単純に転記ミスが多くみなさんが混乱されていると思います。

関数： heap_sortの内容は下記ですので
★マークの所が抜けています。

〇 整数型の配列: heap_sort( 整数型の配列: list ) 
 for ( i を list の要素数 から 1まで1ずつ減らす ) 
  list[ 1 ] と list[ i ] を入れ替える★
  list ← heap( list, 1, i - 1 )
 endfor 
 return list 

質問されている「10と7」の入れ替えは、関数：heap_sortの★マークで行われています。
また、関数：heapの内容についても「max←root」などの転記ミスにより誤植のように勘違いが発生しています。

重点対策は、トレースや各行の説明も細かに説明があり、とても良い書籍ですよ♪
（ただ、、、誤植が修正されるまでは、初心者には厳しいと思いますけどね。。。）

No.24の正しいトレースは以下のようになります。

>list = {1,7,4,8,10}
>heap(list,2,4)を実行する

根の8と末尾の1を入れ替えた後ならheap(list,1,3)が正しい。

>left=2
>right=3

heap(list,1,3)なら正しいが、heap(list,2,4)では誤り。

>max=1

参考書通りならmaxはここでは代入されない。

>bottom=2

bottomへの代入は行われていない。

>if(left<=bottom)and(list[left]>list[root]) 
>   2    2           （2） 7 （1） 1

leftは2,bottomは3なのでandの前半の条件はtrue
list[2]は7、list[1]は1なので後半の条件もtrue

全体の条件式もtrueなのでif文の中を実行する

>max←left      成立したのでendifまで飛ぶ
maxに2が代入される。elseは実行されない。

>if((right<=bottom)and(list[right]>list[max])  不>成立 endifまで飛ぶ
>    3      2            （3）4    （1）7
rightは3,bottomは3なので前半の条件式はtrue
list[3]は4、list[2]は7なので後半の条件式はfalse

全体の条件式はfalseなのでif文の中は実行されない。

>if(max≠root)
>    2    1
maxは2,rootは1なので条件式はtrue
if文の中を実行する。

>list[root]とlist[max]を入れ替える
>     1            7
list[1]は1、list[2]は7なので1と7を入れ替えて、listは｛7,1,4,8,10}になる。

>list←heap(list,max,bottom)
heapの再帰呼び出し
list={7,1,4,8,10}、maxは2,bottomは3なので
heap(list,2,3)が呼び出される。

再帰部分は自分でやってみてください。

最後までありがとうございます。