InitHeap って なんですか？

Question

ヒープソートで昇順に整列させる問題です。
画像の赤線で囲んだ部分の処理がわかりません。InitHeap(Num) とはどういうことなのでしょうか。Num=50 だったら節が５０個あるヒープが作られるということですか？
また次のループ分の処理 Swap と MakeHeap もよくわかりません。多分取り換える処理とのとヒープを作る処理だと思うのですが、引数をどう扱えばいいのかわかりません。どなたか教えてください。


InitHeap の処理ですでに正しくヒープが形成されている、という認識でいいのでしょうか。

Answer 1

ヒープソート(Javaアプレット注意)

最初にヒープを構成する際に，「親が2つの子のどちらよりも大きい」というルールにしたがって並び替える必要があります．その手順をInitHeapが担っていると考えられます．
MakeHeapもヒープの構成ですが，InitHeapとの違いは，InitHeapはヒープの下から入れ替えを行って全体を走査するのに対し，MakeHeapはヒープの上から入れ替えを行っている点です．
InitHeapにより親＞子のルールが頂上と確定した末尾以外では必ず成立しているので，次に頂上に持って来るべき最大値は頂上とその子である2つの節のいずれかになります．入れ替えが発生しなかった節ではその下の節は入れ替える必要が無いため，入れ替えた先でのみ，次の入れ替えが発生する可能性があります．それを逐次チェックしていくのがMakeHeapです．

Comments

[退会済みユーザー]

昨日に引き続きありがとうございます。質問を編集したので見ていただけないでしょうか。

[swordone]

「最初にヒープを作成」とあるのでそういうことでしょう．具体的な説明が無いのであればそういうものと割り切るしか無いのではないでしょうか．
そもそも「ヒープ」というものが「親≧子」または「親≦子」の構造であるという定義ですので．

[退会済みユーザー]

「InitHeap の処理で正しいヒープが形成される」として問題を進めていったら無事解くことができました。Swap と MakeHeap の処理も問題文をよく読んだらわかりますね…リンク先の説明でヒープソートがよく理解できました。ありがとうございます。

Answer 2

ヒープソートのアルゴリズムを問う問題ですね。

せっかくの演習問題なので･･･
（無料の会員登録は必要ですが）是非とも こちら の解説をよく読んで考えてみてください。

ヒープというのは整列作業用の領域の事で、いわば作業用に確保した配列変数です。
ヒープソートでは、まだ整列の終わっていない部分列の中からある条件を満たすような部分を見つけてヒープへ入れたり出したりすることで並べ替えを行います。

前述の解説の２ページ目にある実例を当てはめてみると分かりやすいかもしれません。

是非とも頑張ってください。

Comments

[退会済みユーザー]

ありがとうございます。質問を編集したので見ていただけないでしょうか。