Processing math: 0%
スキップしてメイン コンテンツに移動

heap structure

Introduction

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 
  1. add data
  2. 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.

Rooted tree is tree as follows.




The node is spread from node 1.

Specially, binary tree is as follows.




Characteristic of this graph is separated to two node and node clogged from above and left side.
Top node of this graph is called root.
For example, node 1 is called parent of node 2. The node 4 and node 5 is children of node 2. node 8,9,10,11,12 is called leaf.

Heap
The heap structure is data structure expressed priority queue by using binary tree.
The priority queue want to 
  1. add data
  2. pick up minimum data (and remove) 
.

Firstly, adding data to heap structure.
1. attach new data in last node of graph.
2. next, if c is younger than D, D is replaced by C.

3. repeat 2 until that parent of C which younger than C is not exists.

Secondly, Picking up minimum data.
1. pick up A
2. copy last node to root.
 3. remove last node E

4. Swap E and child node B or D if child node is younger than E. If all child is younger than E, swap E and minimum child.

this method is needfully for keeping heap structure.


Implementation
When you implement heap structure, use array or list.
The number of child node is 2 times parent node number + 1 or 2 times parent node number +2. The 2 times parent node number + 1 is left child. The 2 times parent node number + 2 is right child.





This gif is value of array of heap structure. I add 10 data and pick up 10 data.

Heap sort
heap sort is sort method by using heap structure. The random array sorted by adding and picking heap structure.

This gif is value of array. The value picked up from heap structure.


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 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 f は次のような条件を満たす関数です。. f はn次元ベクトルから実数値を出力します。 このベクトルは次のように表せます。 x = [x_1,x_2,,,,x_n] \forall x_i , i \in {1,2,,,n}, f は二回偏微分可能です。 定義 ヘッセ行列は \frac{\partial^2}{\partial x_i \partial x_j}を (i,j)要素に持ちます。 よってヘッセ行列は次のように表せます。 \[ H(f) = \left( \begin{array}{cccc} \frac{\partial^ 2}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & &\ldots \frac{\partial^2 f}{\partial x_1 \partial x_n} \\ \frac{\partial^ 2 f}{\partial x_1 \partial x_2} & \frac{\partial^ 2 f}{\partial x_2^ 2} & \ldots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \frac{\partial^ 2 f}{\partial x_n \partial x_2} & \ldo...
コメントを投稿
続きを読む

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...
コメントを投稿
続きを読む

カーネル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としま...
コメントを投稿
続きを読む