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

ヒープ構造

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 今日は、ヘッセ行列を用いたテイラー展開について書こうと思います。 これは最適化を勉強するにあたって、とても大事になってくるので自分でまとめて残しておくことにしました。とくに、機械学習では最適化を必ず行うため、このブログのタイトルにもマッチした内容だと思います。 . 概要 ヘッセ行列の定義 ベクトルを用いたテイラー展開 関数の最適性 ヘッセ行列の定義 仮定 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...
コメントを投稿
続きを読む

Rolle’s theorem

Introduction 日本語 ver This post is written Rolle’s theorem. The mean-value theorem is proved by Rolle’s theorem. I will write Mean-value theorem at a later. I introduce Maximum principle because proving Rolle’s theorem need Maximum principle. Maximum principle It is very easy. f is continuous function on bounded closed interval.\(\implies\)** f have max value.** Proof This proof is difficult. I write this proof in other posts. Maximum Principle Rolle’s theorem f is continuous function on [a,b] and differentiable function on (a,b). \[f(a) = f(b) \implies \exists ~~c ~~s.t~~ f'(c) = 0 , a<c<b\] Proof f(x) is constant function \[\forall c \in (a,b) , f'(c) = 0\] else when \(\exists t ~~s.t~~f(a) < f(t)\), \(\exists c ~~s.t~~ \max f(x) = f(c)\) by Maximum principle I proof \(f'(c)=0\) f is differentiable on \(x = c\) and \(f(c) >= f(c+h)\). Thus \[f'(c) = \lim_{h \rightarrow +0} \frac{f(c+h) - f(c)}{h} \leq 0\] \[f'(c) = \lim...
コメントを投稿
続きを読む

Pythonでグラフ理論

Introduction English ver 今日はnetworkxというpythonのモジュールについて書きます。 グラフ理論の定義などの情報は ここ の記事に書いてあります。 この記事ではグラフ理論の中身については扱いませんが、Pythonでのnetworkxというモジュールについてメモをしておきます。 Networkx Python3にはnetworkxはすでに入っています。 Python2の方はpipを使ってinstallしてください。コマンドラインで以下のコマンドを実行します。 pip install networkx ではNetworkxを使ってグラフを作っていきます。 初めにimportをしてインスタンスを作っていきます。 import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() 次にグラフにノード（頂点）とエッジ（枝）を入れていきます。 G.add_node(1) # add Multiple nodes G.add_nodes_from([2,3,4]) G.add_edge(1,2) # add Multiple edges G.add_edges_from([(3,4),(1,2),(4,6)]) ではこのGのグラフを描画していきましょう。 以下のコードで描画できます。 nx.draw(G) plt.show() Networkxはたくさんの関数を持っています。 また、随時追記していきたいと思います。 Reference https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f http://akiniwa.hatenablog.jp/entry/2013/05/12/012459
2 件のコメント
続きを読む