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

ヒープ構造

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:

コメント

コメントを投稿

このブログの人気の投稿

最尤推定

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 件のコメント
続きを読む

Implementation of Robbins monro

Robbins monro の実装 sorry, this page is Japanese only.   今回はRobbins monro の実装をしてみました。 Robbins monroは確率勾配降下法の学習率を入りテーション回数の逆数で割っていくものです。 使っているprogram言語はpython 3です。osはwindowsです。(macほしい...) アルゴリズム 確率勾配降下方とは目的関数の最適解を求めるアルゴリズムです。目的関数をf(X)とすると、手順は以下のようになっています。 初期学習率$n_0$を決めます。訓練データDを用意します。この訓練データは複数の初期値の集まりです。 訓練データから一つ初期値をランダムに取り出し、これを$x_0$とし、最初の予測値とします。 次の式に現在の予測値$x_0$を代入し、新たな予測値$x_{n+1}$を得ます。$$x_{n+1} = x_{n} - \frac{n_0}{n} grad f(X_n)$$ 収束して入れば4へ、収束していなければ2で得られた値$x{n+1}$を新たに$x_n$としてもう一度2を行う。 訓練データを一周していなければ2へ、一周していれば各初期値から得られた解の中から目的関数を最も小さくするものを選ぶ。　　 実装例 以下の目的関数を最小化させてみましょう。 $$f(x,y) = (x-2)^2 + (y-3)^2 $$ コマンドラインでpythonを実行していきます。 予想通り、（２，３）という解を導き出してくれました。目的関数が簡単だったので、初期値をどの値でとってもばっちり正解にたどり着いてくれました。 CODE 以下にRobbins monroの関数だけ置いておきます。 こちら にすべてのコードを載せています。 def Robbins_monro(function,grad,number_variable_gradient): init_learning_rate = 1.5 stepsize = 1000 init_value = np.array([range(-1000,1020,20) for i in range(number_v...
コメントを投稿
続きを読む

離散フーリエ変換

Introduction English ver 今日は離散フーリエ変換について書きます。 現在、シグナル解析についてのpdfを作成中です。このpdfは github で公開中です。 シグナル解析は、courseraのレクチャーで勉強中です。 ここ にリンクを貼っておきます。 pdfは随時更新中です。
2 件のコメント
続きを読む