ヒープ 二分木 違い 9

公式によるとheappushとheappopを別々に行うよりも、これらの関数を使う方が効率的に行えるとの事。 ヒープを利用するデータ構造（優先度付きキュー）について 2.1. どのようにすれば良かったのか・・？, 解説を見て学んだのが "優先度付きキュー" というアルゴリズム。 2 リストをソート ( sort() ) して一番後のインデックスにある要素（＝最大値）を取る, you can read useful information later efficiently. すると、そのヒープの最小値には元の最大値×(-1)した要素が来る。 build_heap 関数によって、もともとの配列を最大ヒープへと並び替えています。, その後、whileループを使って、ヒープの先頭と末尾の入れ替えを繰り返し行っています。, 40行目のif文で、親子間の交換があった場合に、さらにその下でも同様の処理を繰り返すようになっています。, 一見複雑に見えますが、前の章でしっかりと動作を確認しているため、それと照らし合わせてみることで、理解できると思います。, ヒープソートは、割と重要だったりするので、ここまで読んで理解できなかった場合は、もう一度アルゴリズムの流れを確認してみてください。, 次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。, 現在20歳。とある国立大学の学部2年生。 この章の概要です。 1. 従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。二分探索木では通りがけ順探索はノードを大きさ順（あるいは大きさの逆順）に調べることになる。, 奥優先探索ともいう。根からできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。一般のグラフと異なりこれまでに訪れたノードを全て記憶しておく必要はない。というのも木には閉路がないからである。行きがけ順、通りがけ順、帰りがけ順探索はすべてこれの特殊な例である。, ノードごとに値が割り振られているとする。あるノードの左の子およびその全ての子孫ノードの持つ値はそのノードの値より小さく、右の子及びその全ての子孫ノードの持つ値はそのノードの値より大きくなるように構成した二分木を二分探索木 (binary search tree) という。二分探索木を通りがけ順に探索すると、各ノードの値を大きさ順（あるいは逆順）に得ることができる。, このような木を用いると二分探索は容易になる。目的とする値を x とすると、根から始めて、, 二分探索木の検索効率が最高になるのは、木の高さが最低な時で、即ち根から各葉までの高さができるだけ等しくなった場合である。そのような二分探索木を平衡二分探索木と呼ぶ。詳細は平衡二分探索木を参照されたい。, 半順序集合を二分木で表現したもので、ヒープ、二分ヒープ、バイナリヒープと呼ぶ。親子の間で、割り当てられた値について 親 ≤ 子、ないしは 親 ≥ 子の関係が必ず成立するものをいう。前者の場合根が最小の値、後者の場合、根が最大の値をもつことになる。詳細はヒープや二分ヒープを参照されたい。, 図の例では、二項演算子を用いた算術式を二分木で表現している。この式を逆ポーランド記法、中置記法、ポーランド記法で記述すると、それぞれ, となり、左優先の帰りがけ順、通りがけ順、行きがけ順に相当する。強調部分は図で点線で囲った部分木である。部分木が二分木であることは、式の項もまた式であることとよく対応する。, 簡潔データ構造は情報理論で求められる最小の領域のみを消費するデータ構造である。 »å­—の大きい方向) に向かってチェックしていきます。, まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。, このアルゴリズムを Haskell でプログラムすると次のようになります。, 関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。引数 h は最後の要素の位置を表します。実際の処理は局所関数 iter で行います。, 最初に、n の子 c1 を求めます。これが h よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。この処理を局所関数 selectChild で行っています。もう一つの子を c2 とすると、c2 が h より大きければ c1 を返します。そうでなければ、compItem で c1 と c2 を比較して小さな子を選びます。, 次に、selectChild で選んだ子 c と親 n を比較し、親が大きい場合は swapItem で親と子を交換します。それから、iter を再帰呼び出しして次の親子関係をチェックします。親が子以下の場合はヒープの条件を満たしているので処理を終了します。, 最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff の 0 番目にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。, ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。次の図を見てください。, 配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。, あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は関数 downheap を使うと次のように簡単にプログラムできます。, 後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。, それでは、ヒープを使って「優先度つき待ち行列 (priority queue) 」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。, 優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。最初に作成する関数を示します。, データ型は Heap a とし、データ構築子を Heap としました。第 1 引数が配列 (ヒープ) の大きさ (Int)、第 2 引数が要素の個数 (IORef Int)、第 3 引数が配列を表します。関数 makeHeap n は大きさが n の空のヒープを生成します。配列と IORef を生成して Heap に格納して返すだけです。, 関数 fromList はリストからヒープを生成します。リスト xs の要素数を length で求めて変数 n にセットし、n / 2 - 1 の値を変数 m にセットします。配列本体は newListArray で生成し、mapM_ で m 番目から 0 番目の要素に downheap を適用してヒープを構築します。, 次はデータを追加する関数 insert を作ります。, 最初にヒープに格納されているデータ数を求めて変数 c にセットします。c がヒープの大きさ size 以上の場合、ヒープは満杯なのでエラーを送出します。そうでなければ、配列の c 番目に x を挿入し、upheap でヒープを再構築します。データの個数 cnt を +1 することをお忘れなく。, 次は最小値を取り出す関数 deleteMin を作ります。, 最初にデータの個数を求めて変数 c にセットします。c が 0 以下の場合、ヒープは空なのでエラーを送出します。そうでなければ、配列 buff の 0 番目の要素を取り出して変数 x にセットします。次に、データの個数を -1 します。データが残ってる場合じはヒープを再構築します。最後尾の要素と 0 番目の要素を swapItem で交換し、downheap でヒープを再構築します。最後に x を return で IO に格納して返します。, あとのプログラムは簡単なので説明は割愛いたします。詳細は プログラムリスト１ をお読みください。, それでは実際に実行してみましょう。. 完全 2 分木とは、根（ルート）から葉（リーフ）までの深さがすべて等しいか、あるいは、1 つだけ深い葉がある木のことです。. 本記事では、基本的なソートの一種である「ヒープソート」のアルゴリズム解説・C言語による実装を確認していきます。, アルゴリズム解説では、図を用いた解説を行うため、イメージしやすい構成となっています。, ソートは、アルゴリズムの中でも非常に基本的な分野なので、是非この機会にマスターしましょう。, ヒープソートの計算時間は、\(O(nlog(n))\)であるため、ソートの中では高速に動作する部類です。, ヒープソートのアルゴリズムをわかりやすく説明するために、以下のように、順を追って解説を進めていきます。, 二分木はポインタを使用して実装することが一般的ですが、普通の配列を使用して実装することで、アクセス時間が短縮できるという利点があります。, 画像からわかるように、配列の先頭がルートとなり、添え字が１, ２の要素は深さ１のノード、添え字が3，4，5，6の要素は深さ２のノード、、、といった具合です。, 何か特別な操作をしたというよりは、「横一列の配列を、こんな感じの二分木として扱いますよ」という、ただそれだけのことです。, ヒープは、形式的に配列の見方を変えるだけなので、以下のような二分木として扱うことになります。, ヒープソートでは、最大ヒープという並び方を利用するので、こちらの説明もしておきます。, 最大ヒープでは、二分木として見た場合に、ある条件を満たすように配列を並び替えます。, その条件は、すべてのノードにおいて「親」＞「子」の関係が成り立つ、というものです。, 例えば、さきほど上で確認した配列を最大ヒープに並び替えると、以下のようになります。, ちなみに、最小ヒープというものもありますが、これは最大ヒープの逆だと思ってもらえればOKです。, では、最大ヒープの構造を踏まえた上で、これをどのように利用するのかを見ていきましょう。, ここでは、具体的な処理を確認する前に、ザックリとソートの手順を図で確認していきます。, これは、言葉で説明するよりも図を見た方がわかりやすいので、さっそく図へ移りましょう。, ヒープのてっぺんは、配列の先頭なので、最大値を取得するまでの計算時間は\(O(1)\) で済みます。, 「ヒープサイズを１つ減らす」、というのは、単純に配列の末尾を無いものとして扱うということです。, これは、もともとの配列における最大値の次に大きな値が、配列の先頭に移動していることになります。, 今回、配列中の最大値「９」は、ヒープに含んでいないため、その次に大きな「８」がヒープのてっぺんに来ている、ということです。, このとき、「９」はヒープから除外して考えているため、ヒープの末尾は「１」になります。, ここまで見ると察しがつくかと思いますが、あとはこれを繰り返すだけで、配列の後ろから順番に大きな値が並んでいきます。, イメージとしては、木のてっぺんにあるヒープの最大値を、ひたすら配列の奥へと詰め込んでいく感じです。, 今回は、「８」と「９」をヒープに含んでいないため、ヒープの末尾は「３」になりますね。, 配列の中で、ヒープに含まれない部分だけに着目すると、こんな感じでソートが進みます。, ソートの全体的な流れを確認することができたので、残りは具体的なアルゴリズムを確認するだけです。, ヒープソートの流れはすでに確認済みであるため、ここでは、「いかにして最大ヒープへと並び替えるのか」を解説します。, 最大ヒープへ並び替える方法さえわかれば、あとは上で確認した処理を繰り返すだけでソートできますね。, なので、ここは単純に、「親」＜「子」となっている部分を入れ替えていけばよさそうです。, では、その部分を入れ替えていきましょう、と言いたいところですが、一体どこから手を付けるべきでしょうか。, 気になる方は、下側から手を付けるパターンを確認したあとに、同様の処理を上からやってみてください。, つまり、上の図で言うと、「６」→「９」→「３」→「７」→　、、、といった具合です。, 確認してみると、これは、すべてのノードにおいて「親」＞「子」の関係が成り立っていますね。, 最初に、 »å­—の大きい方向) に向かってチェックしていきます。, まず、2 つの子の中で小さい方の子を選び、それと挿入したデータを比較します。もしも、ヒープの条件を満たしていなければ、親と子を交換し、その次の子供と比較します。これを、条件を満たすか、子供がなくなるまで繰り返します。このアルゴリズムを Python でプログラムすると次のようになります。, 関数 downheap はヒープを満たすように n 番目の要素を葉の方向へ移動させます。n + 1 番目から最後までの要素はヒープを満たしているとします。最初に配列 buff の大きさを求めて変数 size にセットします。次に、n の子 c を求めます。これが size よりも大きければ処理を終了します。そして、もう一つの子 (c + 1) がある場合は、小さい子を選択します。そして、buff[n] <= buff[c] が真であれば、ヒープの条件を満たしているので、break で処理を終了します。そうでなければ、n 番目と c 番目の要素を交換して処理を繰り返します。, 最小値を取り出したあと新しいデータを挿入しない場合は、新しいデータの代わりに配列 buff の最後尾のデータを buff[0] にセットしてヒープを再構築します。上図の例でいえば、100 を buff[0] にセットして、ヒープを再構築すればいいわけです。この場合、ヒープに格納されているデータの個数は一つ減ることになります。, ところで、n 個のデータをヒープに構築する場合、n - 1 回 upheap を呼び出さなければいけません。ところが、すべてのデータを配列に格納したあと、ヒープを構築するうまい方法があります。次の図を見てください。, 配列を前半と後半の 2 つに分けると、後半部分はこれより下にはデータが繋がっていない葉の部分になります。つまり、後半部分の要素は互いに関係がなく、前半部分の枝にあたる要素と関係しているだけでなのです。したがって、後半部分だけを見れば、それはヒープを満たしていると考えることができます。, あとは、前半部分の要素に対して、葉の方向に向かってヒープの関係を満たすよう修正していけば、配列全体がヒープを満たすことになります。この処理は関数 downheap を使うと次のように簡単にプログラムできます。, 後ろからヒープを再構築していくと考えるとわかりやすいでしょう。この方法の場合、要素 n の配列に対して、n / 2 個の要素の修正を行えばよいので、最初に説明したヒープの構築方法よりも速くなります。, それでは、ヒープを使って「優先度つき待ち行列 (priority queue) 」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。, 優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。Python には配列をヒープとして扱うモジュール heapq がありますが、本稿ではクラスとして実装してみましょう。クラス名は PQueue とします。定義するメソッドを表に示します。, メソッド名は enqueue, dequeue としてもよかったのですが、モジュール heapq の関数が heappush, heappop になっているので、このプログラムでは push, pop としました。また、データを追加する関数を insert とし、最小値を取り出す関数を delete_min としている参考文献もあります。, プログラムは次のようになります。, メソッド __init__ は、引数の配列 buff をコピーして、インスタンス変数 buff にセットします。そして、関数 _downheap を呼び出してヒープを構築します。downheap と upheap は内部で使う関数なので、名前にアンダーバーを付けました。データを追加するメソッド push は簡単です。append で配列 buff の最後にデータ x を追加し、関数 _upheap を呼び出してヒープに挿入します。, 次は、最小値を取り出すメソッド pop を説明します。pop はデータがなければエラー IndexError を送出します。それから、最小値 self.buff[0] を取り出して変数 value にセットし、最後尾のデータを pop で取り出して変数 last にセットします。もし、配列 buff にデータが残っていたならば、last を self.buff[0] にセットして _downheap でヒープを再構築します。最後に return で最小値 value を返します。, メソッド peek と isEmpty は簡単なので説明を割愛いたします。詳細は プログラムリスト２ をお読みください。, 実行結果は次のようになります。, お気楽 Python プログラミング入門第 2 回.