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

ヒープ構造

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:

コメント

コメントを投稿

このブログの人気の投稿

heap structure

Introduction 日本語 ver Today, I will write about heap structure. The heap structure is one of the data structure. My reason of studying heap structure is that I joined seminar of Ritsumeikan Univ. I used this  slide  in seminar of Ritsumeikan Univ. Overview data structure binary tree heap Implementation heap sort Data structure I will explain about data structure before explaining about heap. Data structure is how to keep data. Data structure is selected on the basis of operation which you want to.  Heap belong to data structure called priority queue. priority queue have purpose which  add data pick up minimum data (and remove)  Binary Tree Let, E and V are sets. The element $e \in E$ is called edge. The element $v \in V$ is called node. g:E->V×V is map to V × V from E. (E,V,g) is called graph. For example, The arrows are edge. The circles are node. This is expressed map. It is possible to go to node 3 from 1....
コメントを投稿
続きを読む

最尤推定

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

LIMIT and user variable in MysQL

Problem 日本語 ver I want to use this query in PROCEDURE. SET @user_variable = FLOOR(RAND()*10); INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET @user_variable; This query want to substitute 1 for the @user_variable 'th line of columns_name, but this query does not work. A cause is that LIMIT and OFFSET does not user variable. Solution SET @user_variable = FLOOR(RAND()*10); PREPARE SET_STMT FROM 'INSERT INTO  Table_name (columns_name) VALUES (1) FROM Table_name ORDER BY RAND() LIMIT 1 OFFSET ?;';  EXECUTE SET_STMT USING @user_variable; Conclusion, if you want to use user variable with LIMIT or OFFSET, use PREPARE STATMENT. Reference http://techtipshoge.blogspot.com/2011/10/limit.html
2 件のコメント
続きを読む