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

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.

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

add data
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

このブログの人気の投稿

カーネル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 今日は、変分法の可視化を実装しました。変分法は、汎関数を最小化させるために使われます。汎関数とは、関数の関数のようなものです。変分法については、 [1] , [2] , [3] , [5] , [6] などを参考にしてください。概要汎関数実装可視化汎関数今回は、次のような汎関数を使います。

$F(x) = \sqrt{1+(\frac{du}{dx}(x))^2}$

$l(u) = \int_{0}^{1} \sqrt{1+(\frac{du}{dx}(x))^2} dx$ l(u)はu(x)という曲線の長さです。.

$u(0)=a$ and

$u(1)=b$ という制約のもと、

$l(u)$ を最小化したいといます。最適な

$l(u)$ は

$u(x) = (b-a)x+a$ となります。 (0,a) から (1,b)への直線になっているのがわかります。これは、

$l(u)$ は

$u$ の曲線の長さなので、これを最小化するためには直線が一番であることが直観的にわかります。変分法での導出は、 [5] を参考にしてください。実装変分法における最適な曲線とそうでない曲線の違いを可視化する実装をしました。

$u_A$ を

$u_A = (b-a)x+a + A sin(8t)$ とします。

$A sin(8t)$ は

$u$ から話す役割を持ちます。.

$A \in [0,0.5]$ であり、もし

$A=0$ であれば、

$u_A=u$ です。 github でcodeを公開しています。可視化上側の画像は

$u_A(x)$ を表しています。下側の画像は

$l(u_A)$ の値を表しています。

$u_A(x)$ が

$u$ に近づくほど、

$l(u_A)$ が小さくなることがわかります。 Reference [1] http://www2.kaiyodai.ac.jp/~takenawa/optimization/resume10-4.pdf [2] http://hooktail.sub.jp/mathInPhys/brach...

ダイクストラ法

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))に減らせます。ヒープ構造で現時点での...

journey of Froakie (ケロマツの旅路)

このブログを検索

heap structure

ラベル

コメント

コメントを投稿

このブログの人気の投稿

カーネルK-means 理論編

変分法の可視化

ダイクストラ法