【ヒープの作り方】

データ構造やアルゴリズムについての質問です。
「ヒープ」を用いてソートができたりすること、
ヒープへ挿入や、ヒープからの削除は分かるのですが、
そもそもヒープの作り方が分かりません。

≪作り方≫
ある要素の集合が与えられたとき、
１つ目の値をルートにもってくる
２つ目の値をルートと比較し、子≦ルートとなるように追加
３つ目の値をルートと比較し、子≦ルートとなるように追加
４つ目の値をルートの左の子と比較し、子≦ルートの左の子、かつルートとも比較
.....
という風に要素の集合から要素がなくなるまで続けるので正しいでしょうか？

それとも初めに与えられた要素の集合を
ひとまず要素数分の２分木構造に割り当て、
ヒープが成り立つように、あとから値の交換を
行うのでしょうか？

いま、要素の集団は配列のように順番が決まっているとして
考えています。

≪取り出しと削除≫
値の「取り出し」と「削除」は別物。という認識は正しいでしょうか？
(1)取り出し...末端の最も右の葉をルートにコピーし、ヒープを再構成。
⇒ルートの値を取り出す。
(2)削除...削除したい値を削除し、その子孫を繰り上げる。

詳しい方がおられましたら、ご指摘、アドバイス等
どうぞよろしくお願い致します。

No.3 ベストアンサー 回答者： Tacosan 回答日時： 2014/08/01 00:10

配列として与えられたデータからヒープを作るだけなら

1. 空のヒープを作って 1つずつデータを追加する
2. 配列に対していろいろ処理して最終的にヒープにする
のどちらも可能です. やってることがわかりやすいのは 1 だけど 2 の方が速く, n個のデータがあるとき 1 が O(n log n) 時間に対して 2 は O(n) 時間.

でいちおう「取り出し」はそれでいいといえばいいです. ただし, 「末端の最も右の値をルートにコピーし、ヒープを再構成する」とはいってもその「末端の最も右」のノードは使わなくなってしまうので, 実務的には「末端の最も右の値とルートの値を交換してからヒープを再構成する」のが普通です. あと, そもそも「取り出す」といったときに「ルートの値をとってくる」だけで「ルートの値を取り除く」までは想定しない可能性があるので, もうちょっと正確な表現をすべきだとは思います.

「削除」ですが, 「削除したい値を削除し、削除した頂点以下のノードを再構成する」は (少なくとも素朴に読む限り) ダメです. TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね. これも上の「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.

この回答へのお礼

回答頂きありがとうございます！
とても分かりやすい説明でした。

＞TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね.

確かにそうでした、ヒープは葉まですべて詰まっていなければ
いけませんもんね！

＞「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.

了解致しました！

お助けいただき、本当にありがとうございました。

お礼日時：2014/08/01 11:17

No.2 回答者： Tacosan 回答日時： 2014/07/31 15:04

作り方自体はどっちでもいいです. 後者の方が速いけど.

「≪取り出しと削除≫」のところは.... 何を言っているのかわからない. 「取り出し」は「⇒」が意味不明だし (ヒープを再構成してからルートの値を取り出すということ?), 「削除」にしてもそれだけではヒープにならない.

この回答への補足

回答頂きありがとうございます！

＞作り方自体はどっちでもいいです.
そうなんですか！？いろいろ調べたのですが
情報が錯そうしてこんがらがっていました。驚きです。
私の１つ目の方法は、「挿入の繰り返し」といった感じです。

＞≪取り出しと削除≫～何を言っているのかわからない
言葉足らずで、すみません。
「取り出し」は、
ソートの際にヒープ完成後、ルートの値を取り出すことを言っています。
ルートの値を取り出し、末端の最も右の値をルートにコピーし、ヒープを再構成する。その繰り返しでヒープソートができるのだろうと思っています。が正しいでしょうか？
「削除」は、削除したい値を削除し、削除した頂点以下のノードを再構成するだけではだめでしょうか？

お手数をお掛けしてしまい、大変恐縮ですが
よろしくお願い致します。

補足日時：2014/07/31 15:21

No.1 回答者： trytobe 回答日時： 2014/07/31 14:35

枝分かれが２分岐でしかないツリー構造のうちでも「２分木」というもので、

その根っこ（といいながら良く図の上側にある）のほうが枝の先（下側）よりも小さい、逆に言えば、枝の先（下側）のほうが大きいような並びでツリーができている

というのがヒープです。あとは、ヒープソートの図解を見たほうが、イメージしやすいかと思います。

９．ソーティング（ヒープソート） | TECHSCORE(テックスコア)
http://www.techscore.com/tech/C/9.html/

ヒープソート
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/al …

ヒープソート - Google 検索
http://www.google.co.jp/search?q=%E3%83%92%E3%83 …

この回答への補足

回答頂きありがとうございます！

「挿入」と「ヒープの作成」が区別できずにいます。

９．ソーティング（ヒープソート） | TECHSCORE(テックスコア)より
「最初はどの部分木もヒープではありませんが、」一番末端の右端にある部分木（９．１の図の場合は「4」を根とする部分木）から順に上記の処理を実行していけば、木全体がヒープになります。
ということは、
私の上記の方法(=挿入の繰り返し)は間違っているという認識でよろしいでしょうか？

お手数をお掛けしますが、
よろしくお願い致します。

補足日時：2014/07/31 15:09