スキップしてメイン コンテンツに移動

ヒープ構造

Introduction

今日はヒープ構造について書きます。ヒープ構造はデータ構造の一種です。ちょうど大学の自主ゼミグループのセミナー合宿に参加させてもらい、そこでグラフ理論を勉強したので、メモをしておこうと思います。

 slide はこんなのを使いました。


Overview

  • データ構造
  • 二分木
  • ヒープ
  • 実装
  • ヒープソート

データ構造
ヒープ構造の前に、データ構造について、説明します。データ構造とは、データを保存する手法であります。データ構造は、そのデータについてどのような操作を行いたいかによって、最適なものを選ぶことになります。

ヒープ構造はプライオリティキューと呼ばれれるデータ構造を表す方法です。プライオリティキューで行いたい操作は以下の二つです。
  1. データの追加
  2. 最小値の抽出

二分木
まず、グラフを定義します。E と V は集合とし、 $e \in E$、つまりEの要素をedge(枝)と呼びます。また、$v \in V$、つまりVの要素をnodeと呼びます。
g:E->V×V をEからV × Vへの写像とします。この時、.(E,V,g)をグラフを言います。

例えば、次のようなものがあります。


丸いのがそれぞれのnodeで、矢印がedgeになります。
各edgeに対して、始点v1と始点v2を対応させるのが写像gの役目です。


根付き木とは次のような木のことです。



これはnode1からnodeが二つずつどんどん派生していっています。

特に、次のような木を二分木といいます。



特徴は、ノードが上からなおかつ左から敷き詰められています。一番上のノードを根といいます。また、例えば2を基準にすると、1は2の親、4,5は2の子、3は2の兄弟、8,9,10,11,12は葉と呼ばれます。

ヒープ
ヒープ構造はプライオリティキューを二分木で表現したものです。プライオリティキューでやりたいことは次のことでした。
  1. データの追加
  2. 最小値の抽出
.
では、どのようにこの二つの操作を実現するのでしょうか。
初めにデータの追加について説明します。
1. 二分木の最後に追加するノードをくっつける
2.親と比べて、自分のほうが若かったら親と入れ替わる。

3. 2を繰り返して、自分より若い親がいないようにする

こうすることでヒープ構造を壊さずに値を加えることができます。

次に、データの抽出です。
1. Aを取り出す。
2. 根の部分に最後尾のノードをコピーする
 3. 最後尾のノードを削除する

4. 自分の子供のうち、小さいほうと自分を比べて子供のほうが若ければいれかえる。
5.4を自分より年寄りな子がなくなるまで繰り返す。

こうすることでヒープ構造を壊さずに最小値を抽出できる。
大事なのはこの操作の計算量はO(logN)であることです。

実装
ヒープ構造を壊さずにを実装するとき、配列かリストを使います。
子供のノードはの番号は2×親ノード番号+ 1、 2 ×親ノード番号+2になります。 2×親ノード番号+ 1は左側の子供です。 2 ×親ノード番号+2は右側の子供です。

このように、Aの子供はB,C、Bの子供はD,E...という風になっています。


heap構造の実装はこちらのgithubに公開しています。

このgifはヒープ構造を表現した配列に10この値を加えていったあと、10回最小値を取り出したときの配列の値です。

ヒープソート
ヒープソートとは、ヒープ構造から値を取り出すときO(lonN)で最小値を取り出せることを利用したソート方法です。ランダムな配列を一度ヒープ構造に突っ込んで、そのあと、最小値を取り出せば、小さい順になって出てくるということです。

このgifは、最初に移る配列を一旦、heap構造の配列に加えて、取り出していった時の配列の値です。


Reference
https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%E3%83%81%E3%83%A3%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%96%E3%83%83%E3%82%AF-%E7%AC%AC2%E7%89%88-%EF%BD%9E%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E6%B4%BB%E7%94%A8%E5%8A%9B%E3%81%A8%E3%82%B3%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0%E3%83%86%E3%82%AF%E3%83%8B%E3%83%83%E3%82%AF%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B%EF%BD%9E-%E7%A7%8B%E8%91%89%E6%8B%93%E5%93%89/dp/4839941068



Labels:

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

Introduction English ver 今日は、カーネルK-meansの理論について書きます。カーネルK-meansは通常のK-meansの欠点を補うことができます。通常のK-meansの欠点とカーネルK-meansの強みも説明します。もし、まだ御覧になられていなければ、通常の K-means 理論編 の記事を見ていただけるとよいのではないかと思います。 カーネルK-meansの実装編 も併せてご覧ください。 概要 K-meansの弱点 カーネルトリック カーネルK-means アルゴリズム K-meansの弱点 例えば、次のようなデータを用意します。 このデータはK-meansによってうまく分類することはできません。なぜなら通常のK-meansでは、データとプロトタイプのユークリッド距離に依存しているからです。そのため、このような円状に分布しているデータはうまく分類することができません。 プロトタイプとはそれぞれのクラスにあり、そのクラスを代表するようなもののことです。K-meansでは各クラスの平均ベクトルとなります。それゆえ、以下のような分類になってしまいます。 このようなデータではK-meansはうまくいきません。 K-meansで分類できるデータセットは次のように各クラスで固まっている必要があります。 カーネルK-meansはK-meansの弱点を補います。 カーネルトリック 初めに、カーネルトリックを説明します。 線形分離できないようなデータ$X$を例えば次のように線形分離できるように$\phi(x)$に送る写像$\phi$を考えます。 カーネルは次のように定義されます。 $$K(x,y) = \phi(x)^T \phi(y)$$ $\phi$を具体的に計算することは難しいですが、$K(x,y)$を計算することなら簡単です。 この手法をカーネルトリックと呼ばれます。 カーネルK means K-meansの目的関数を復習しておきます。 $$J = \sum_{n=1}^{N} \sum_{k=1}^{K} r_{nk} ||x_n-\mu_k||^2$$ ここで、 プロトタイプは$\mu_i ~\forall k \in K$としま...
コメントを投稿
続きを読む

最尤推定

Introduction English ver 今日は最尤推定について加工と思います。これは統計的推定でよく使われる手法です。最尤推定の例も書こうと思います。初めに尤度の説明をし、そのあとで最尤推定の説明をします。 概要 尤度 最尤推定 最尤推定の問題点 尤度 前提条件から得られる観察データを考えます。この時、えられた観測データに対して前提条件が尤もらしい条件であるかの値を尤度といいます。 なにをゆっているのかわからない人がほとんどだと思います。。。 尤度の例を扱っていきます。 コインを投げることを考えます。このコインは確率Pで表、確率1-Pで裏を出すコインだとします。 例えば、100回コインを投げたとき、全て表だったとします。この時このコインが表が出る確率はかなり1に近いことが予想されます。 ではもし、表が出る確率PがP=0.5だとします。この時、表が100回連続で出る確率は$0.5^{100} = 7.88860e-31$になります。あり得ない確率ですね。これがP=0.5としたときのもっともらしさです。つまり、あまり現実的ではないということです。 もしP=0.99とするとき、100回とも表が出る確率は$0.99^{100} = 0.3666....$となります。つまり、P=0.99としたときの尤度は0.36くらいということです。よって、P=0.5よりかは現実見があることになります。まだまだ低い数字ではありますが。 観測データである、100回表が出るという事象を固定したとき、尤度はPを変数としたP(100回表|P)を尤度関数と呼びます。この関数の値を尤度と呼びます。 尤度が高いほうが尤もらしい値、つまり理にかなっているなと感じることができる値ということになります。 例えば、先ほどの例でゆうと、 P=0.5としたときの尤度は7.88860e-31でした。P=0.99としたときの尤度は0.3666でした。よってP=0.5より、P=0.99のほうが尤もらしい自然な値ということになります。 最尤推定 最尤推定とは得られた観測データからデータが依存している分布のパラメーターを推測するための手法です。 最尤推定では尤度を最大化して、最も尤もらしいパラメーターを求めます。 確率密度関数...
3 件のコメント
続きを読む

ダイクストラ法

Introduction English ver 今日は、ダイクストラ法について書きます。ダイクストラ法とは最短距離を求めるアルゴリズムです。地図はグラフで表されます。もし、まだ this page を見ていない方は先にこちらをご覧ください。今回はこの記事を前提としています。このページでは、グラフの定義と、ヒープ構造について書いています。ダイクストラ法ではヒープ構造を使って、かなりの計算量を落とします。 この スライド はダイクストラ法を説明したスライドです。 Overview アルゴリズム 実装 アルゴリズム このアルゴリズムは スタート始点のノードを決める。そして、それをAと名付ける。 各ノードに$d=\infty$を割り当てる。ただし、スタート地点はd=0 Aの隣接ノードのリストをadj_listと名付ける。  For adj in adj_list:  If d of adj > d of A + weight to adj -> d = A + weight to adj. グラフnetworkからAを取り除く グラフnetworkの中で最初のdを持っているノードをAとし、4に戻る。 となっています。 このアルゴリズムを図を用いて説明します。  このグラフを使って説明します。  初めに、スタート地点を決めます。そして、各ノードに$d=\infty$を割り当てます。  Aから始まります。Aの隣接ノードであるBのdを更新します。もし、現在のBよりもAのdとA->Bへの重みを足したもののほうが小さいならdをその値に更新します。同じようにCnのdを更新します。 次にAを取り除きます。  次はBから始まります。Aと同じことをやります。 このダイクストラ法では今のような操作をグラフの全てのノードに×がつくまで続きます。 実装 このアルゴリズムでは$O(log(|V|^2))$という計算量を持っています。最小のdを持つノードを探すのに時間がかかります。 しかし、ヒープ構造を使えばO((E+V)log(V))に減らせます。ヒープ構造で現時点での...
コメントを投稿
続きを読む