質問: 【ヒープの作り方】 データ構造やアルゴリズムについての質問です。 「ヒープ」を用いてソートができたりすること、 ヒープへ挿入や、ヒープからの削除は分かるのですが、 そもそもヒープの作り方が分かりません。 ≪作り方≫ ある要素の集合が与えられたとき、 1つ目の値をルートにもってくる 2つ目の値をルートと比較し、子≦ルートとなるように追加 3つ目の値をルートと比較し、子≦ルートとなるように追加 4つ目の値をルートの左の子と比較し、子≦ルートの左の子、かつルートとも比較 ..... という風に要素の集合から要素がなくなるまで続けるので正しいでしょうか? それとも初めに与えられた要素の集合を ひとまず要素数分の2分木構造に割り当て、 ヒープが成り立つように、あとから値の交換を 行うのでしょうか? いま、要素の集団は配列のように順番が決まっているとして 考えています。 ≪取り出しと削除≫ 値の「取り出し」と「削除」は別物。という認識は正しいでしょうか? (1)取り出し...末端の最も右の葉をルートにコピーし、ヒープを再構成。 ⇒ルートの値を取り出す。 (2)削除...削除したい値を削除し、その子孫を繰り上げる。 詳しい方がおられましたら、ご指摘、アドバイス等 どうぞよろしくお願い致します。
回答: 配列として与えられたデータからヒープを作るだけなら 1. 空のヒープを作って 1つずつデータを追加する 2. 配列に対していろいろ処理して最終的にヒープにする のどちらも可能です. やってることがわかりやすいのは 1 だけど 2 の方が速く, n個のデータがあるとき 1 が o(n log n) 時間に対して 2 は o(n) 時間. でいちおう「取り出し」はそれでいいといえばいいです. ただし, 「末端の最も右の値をルートにコピーし、ヒープを再構成する」とはいってもその「末端の最も右」のノードは使わなくなってしまうので, 実務的には「末端の最も右の値とルートの値を交換してからヒープを再構成する」のが普通です. あと, そもそも「取り出す」といったときに「ルートの値をとってくる」だけで「ルートの値を取り除く」までは想定しない可能性があるので, もうちょっと正確な表現をすべきだとは思います. 「削除」ですが, 「削除したい値を削除し、削除した頂点以下のノードを再構成する」は (少なくとも素朴に読む限り) ダメです. techscore の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね. これも上の「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.