- ベストアンサー
ヒープの作り方
- ヒープの作り方や要素の取り出しと削除などについて詳しく教えてください。
- ヒープはデータ構造やアルゴリズムにおいて重要な役割を果たす概念です。
- 要素の集合からヒープを作る方法や、要素の取り出しや削除の方法について教えてください。
- geamantannn
- お礼率37% (12/32)
- 情報工学
- 回答数3
- ありがとう数1
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (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番だけをヒープとして作り直してもダメだよね. 確かにそうでした、ヒープは葉まですべて詰まっていなければ いけませんもんね！ ＞「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな. 了解致しました！ お助けいただき、本当にありがとうございました。