- ベストアンサー
ヒープの作り方
- ヒープの作り方や要素の取り出しと削除などについて詳しく教えてください。
- ヒープはデータ構造やアルゴリズムにおいて重要な役割を果たす概念です。
- 要素の集合からヒープを作る方法や、要素の取り出しや削除の方法について教えてください。
- geamantannn
- お礼率37% (12/32)
- 情報工学
- 回答数3
- ありがとう数1
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
配列として与えられたデータからヒープを作るだけなら 1. 空のヒープを作って 1つずつデータを追加する 2. 配列に対していろいろ処理して最終的にヒープにする のどちらも可能です. やってることがわかりやすいのは 1 だけど 2 の方が速く, n個のデータがあるとき 1 が O(n log n) 時間に対して 2 は O(n) 時間. でいちおう「取り出し」はそれでいいといえばいいです. ただし, 「末端の最も右の値をルートにコピーし、ヒープを再構成する」とはいってもその「末端の最も右」のノードは使わなくなってしまうので, 実務的には「末端の最も右の値とルートの値を交換してからヒープを再構成する」のが普通です. あと, そもそも「取り出す」といったときに「ルートの値をとってくる」だけで「ルートの値を取り除く」までは想定しない可能性があるので, もうちょっと正確な表現をすべきだとは思います. 「削除」ですが, 「削除したい値を削除し、削除した頂点以下のノードを再構成する」は (少なくとも素朴に読む限り) ダメです. TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね. これも上の「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
作り方自体はどっちでもいいです. 後者の方が速いけど. 「≪取り出しと削除≫」のところは.... 何を言っているのかわからない. 「取り出し」は「⇒」が意味不明だし (ヒープを再構成してからルートの値を取り出すということ?), 「削除」にしてもそれだけではヒープにならない.
補足
回答頂きありがとうございます！ ＞作り方自体はどっちでもいいです. そうなんですか！？いろいろ調べたのですが 情報が錯そうしてこんがらがっていました。驚きです。 私の１つ目の方法は、「挿入の繰り返し」といった感じです。 ＞≪取り出しと削除≫～何を言っているのかわからない 言葉足らずで、すみません。 「取り出し」は、 ソートの際にヒープ完成後、ルートの値を取り出すことを言っています。 ルートの値を取り出し、末端の最も右の値をルートにコピーし、ヒープを再構成する。その繰り返しでヒープソートができるのだろうと思っています。が正しいでしょうか？ 「削除」は、削除したい値を削除し、削除した頂点以下のノードを再構成するだけではだめでしょうか？ お手数をお掛けしてしまい、大変恐縮ですが よろしくお願い致します。
- trytobe
- ベストアンサー率36% (3457/9591)
枝分かれが２分岐でしかないツリー構造のうちでも「２分木」というもので、 その根っこ（といいながら良く図の上側にある）のほうが枝の先（下側）よりも小さい、逆に言えば、枝の先（下側）のほうが大きいような並びでツリーができている というのがヒープです。あとは、ヒープソートの図解を見たほうが、イメージしやすいかと思います。 ９．ソーティング（ヒープソート） | TECHSCORE(テックスコア) http://www.techscore.com/tech/C/9.html/ ヒープソート http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/heap-sort.html ヒープソート - Google 検索 http://www.google.co.jp/search?q=%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88
補足
回答頂きありがとうございます！ 「挿入」と「ヒープの作成」が区別できずにいます。 ９．ソーティング（ヒープソート） | TECHSCORE(テックスコア)より 「最初はどの部分木もヒープではありませんが、」一番末端の右端にある部分木（９．１の図の場合は「4」を根とする部分木）から順に上記の処理を実行していけば、木全体がヒープになります。 ということは、 私の上記の方法(=挿入の繰り返し)は間違っているという認識でよろしいでしょうか？ お手数をお掛けしますが、 よろしくお願い致します。
お礼
回答頂きありがとうございます！ とても分かりやすい説明でした。 ＞TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね. 確かにそうでした、ヒープは葉まですべて詰まっていなければ いけませんもんね！ ＞「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな. 了解致しました！ お助けいただき、本当にありがとうございました。