- テレビ科目
- 情報コース
- 鈴木一史先生（放送大学教授）
- 難易度 ★★★☆☆
- おすすめ度 ★★★☆☆
同じ鈴木先生の講座「アルゴリズムとプログラミング(’20)」の上位互換で、同講座と半分くらいかぶっている。アルプロと比べるとこちらの方が内容が高度で、C言語の程度も高いのだが、テレビ講座の利点を生かし切っておりこっちの方がわかりやすい。毎回動作確認を丁寧に行ってくれて好感度が高い。なお先生はにちゃんねらーでまどマギのファンと思われ、タイトルに関連AAが毎回ちりばめられている。
第1回
イントロと配列について。C言語はある程度知っていることが前提なので、同じ先生のアルゴリズムとプログラミング(’20)を履修してからの方がよいね。
C言語をwindowsで簡単にコンパイル・実行する環境って何があるのかなー。web上でやった方が速い気がする。
( ´∀｀)モナーがいるんだけど。。先生にちゃんねらーじゃん。
テレビ科目で見やすいんだけど、windows3.1味のある古いグラフィックで洗練されてない。
配列ってなんで添え字0から始まるんだろうね。
C言語のrand()ってintの最大値までの値を返すのか。だからrand() % 100 みたいにしないとだめなのね。てっきり0～1の間なんだと思ってたけどそれだと不便だな。
構造体の配列。まあだいたいDBに対応する。固定長だけど。メモリ量が多くなってきたら、mallocで動的確保した方が無難とのこと。ヒープに確保できるので。
スライスって配列をぶった切る関数じゃないの？配列を拡張したものみたいに紹介がされている。
配列へのデータ挿入。最大n個のデータを移動しないといけないから計算量はオーダーnになる。削除も同様。つまり負荷が大きい。
データ探索について。線形探索はこれもオーダーn。二分探索は整列済みの配列に対して行わなければいけない制約があるが高速。図解してくれていてこれはわかりやすい。配列の場所としてlow, mid, hiの値を用意して、探索する値がmidと比べて大小どちらか確認、またlow, mid, hiを設定しなおす…の繰り返し。midにある要素と検索したい値が一致したら終了。
線形探索が遅いことを実践。30万件のデータを30万回検索すると当時の最新のCPUでも18秒。一方、二分探索だと0.02秒。ちなみに事前に要素をソートするqsortも0.029秒しかかかってない。
第2回
スタックについて。スタックと言えばお盆（食器の方）らしい。たしかにそうだね。
先生の手元が常に動いているのが気になる。
swap(頂上と2番目の値を取り換える)、duplicate(頂上のデータをコピーしてpush)って操作は知らなかった。
スタックの実際の実装方法。アルゴリズムとプログラミングの所でも習ったけど、ようやく映像で見られる。まず配列で実装する方法。添え字を保存しておけばOK。ただ配列サイズがいっぱいになる可能性がある。挿入も削除もオーダー1で高速。コード例も映像で見られるからいいな。
スタックを1億個使ってCore i7で動作実験。乱数発生も含めて1秒で終わった。高速ですね。
文字列データについて。Linuxには48万件程度の辞書データが入ってるらしい。文字データとしてこいつを使い、スタックに積む処理も高速で1秒だった。
スタックの応用について。まず文字列の反転。たしかにpopしてけば逆になるな。今後使ってみよう。それから逆ポーランド記法。７８＋（7+8と同じ）のように記述するやり方。どこまでが被演算子かわからないので、7 8 + のように区切りを入れる必要がある。処理方法としては、演算子が出てきたら2回popして計算してpushすればいいってわけ。楽だね。
3 4 + 5 * なら→3 4 をpushした後 + が出てきたから、3, 4 をpopしたあと3 + 4 = 7をpush。次に5をpushしたら * が出てきたから、7, 5をpopして、7 * 5 = 35を計算してpush。これで35が答えになる。逆ポーランド記法ではカッコがいらないことが特徴。
スタックはSTLに入ってますよって話もしてる。STLの場合、可変長になってるだろうから処理速度はどんくらいなんだろうね。
第3回
キューについて。タイトルにキュゥべえ出すなよ。。。先生。。。
キューの構造はわかってるからいいとして、実装が気になる。配列を途中から途中まで使うようなイメージなのか。だから先頭と末尾の添え字が必要。オーバーフローと空のチェックも必要。使っていけばすぐ配列の末尾に達するから、リングバッファ化するしかない。計算量はO(1)。はやい。
C言語のコード例、穴だらけ（MAXが小さいとかリングバッファになってないとか）なんだけど、教育用だから仕方ないか。。
enqueueを1億回やるテスト。1.2秒で終わった。バッファも1億個作ったのな。4バイト変数で4GBか。まあできなくはないか。
stdにもキューがある。queue<int>みたいな。ただ、メソッド名がpushとpopなのでスタックとまぎらわしい。
キューの応用。まず両端キュー。頭と後と両方で追加削除が可能。enqueとdequeueの意味が普通のキューと変わってくるのでわかりづらい。
優先度付きキュー。dequeueのときに、優先度の高いもの（値が小さい場合のことが多い）から取り出される。だからenqueueした順とは限らない。利用例としては、イベントの待ち行列、OSの割り込み、ダイクストラ法、ハフマンコードなど。なのでかなり大事な技術みたい。効率の良い実装が望まれる。配列(n)、順序配列(n)、ヒープ(logn)といった実装があるがヒープが一番効率がいい。配列だとdequeue、順序配列だとenqueueにコストがかかってしまう。
あれ、ヒープの実装はどうやるの？→第14回でやるみたい。
第4回
連結リストについて。汎用的なDBを作るのと同じなんだって。リスト自身が他の要素へのポインタを持ってることまでは把握してる。もしかしてDB自体が連結リストなのかな？
C言語依存の解説だけど、他言語でも実装方法は変えようがないから同じだよな。基本的な関数名は教えてくれるので親切。
ノード作成のコード、head->next->next->next->next->next = NULL とか糞コードに見えるけど意地でもポインタ変数を使わないためにはしょうがないのかな。
nullってナルって呼ぶのが最近の流行りなの？ヌルじゃないの？日本語読みだからダメ？
連結リストって都度メモリ確保してるけど、例えばC#のListなんかはこれ使ってるのかな？それとも配列型で、数が大きくなったらメモリ追加確保なのか？
ノード挿入。先頭、中間、末尾に挿入する場合の3パターンに処理が分かれる。先頭ならheadを更新、中間なら前のノードのnextを変更、末尾ならnextにNULLを入れないといけない。挿入は、メモリの並べ替えをやらなくていいから効率はよい。
実際のコード、毎回引数にheadを入れないといけないのか―。面倒だけどしょうがないか。XMLのオブジェクトが常にdocumentのポインタを必要とするのと一緒かな。
10万件でテスト。0.004秒で終わった。はやっ。ただこれは、全て先頭への挿入だったから。末尾だとどうなるか。12.6秒。毎回ノードを全部たどるから遅い。10万件でもけっこうきついね。そういえば以前、鉄道駅をノードにしてこれをたどりまくるJavaScriptのコードを書いたことがあるけど、遅かった。速くするための工夫がいろいろ必要になるんだな。
ノード1億個を先頭に挿入→4秒。1億ノードの末尾に1個だけ挿入→0.382秒。おそい。
ノード削除。これも先頭、中間、末尾で処理が変わる。先頭ならheadを変える。中間ならノードを繋ぎかえる。末尾なら1個前（これをgetするのが面倒そう）のnextをnullにする。で1個メモリを解放すればいいね。
10万件削除（先頭）の実行時間は0.006秒。楽勝ですね。
第5回
連結リストの応用。まず探索について。連結リストは基本的にシーケンシャルアクセスなので、オーダーはO(n)になる。整列はどうするか。整列済みリストに挿入するなら簡単で、リンクをたどりながらどこに挿入するか判定していけばいい。これもオーダーはO(n)。ソートアルゴリズムはマージソートっぽくなるらしい（要コード例）。
接続は単にnextと他のリストのheadを繋ぐだけだから簡単。マージも楽。分割も簡単。
連結リストでスタックを実装する。pushでheadに1個データを追加する、popでheadから1個データを取っていけばOK。簡単じゃん。計算量も両方ともO(1)。はやい。配列と同じ。しかも容量制限なし。
キューの実装。enquereは末尾に1個データを追加、dequereはhead1に1個データを追加でOK。これも簡単。enquereは末尾のポインタ取っとけばO(1)かな。とっとかないとO(n)だから遅い。実際、末尾まで全部サーチする場合のデータ削除は10万件で12.6秒もかかる。
コード、テレビの画面で見ても理解が難しいことを先生が認めている。そうか？わかりやすいと思うけどな。
連結リストから派生したデータ構造。双方向連結リストとか、環状連結リストとか。前のノードへのポインタを保持する双方向連結リストは、データ量は大きくなるが実装としては妥当な感じがする。便利。近代的プログラミング言語でも標準的らしい。stdでも<list>で提供されているらしい。C#のListも同じか？
環状連結リストはどういう場合に便利なのか謎。→OSのプロセススケジューリングで使われているらしい。たしかに、終わるまでずっと繰り返すような処理には向いてる。で、当然環状双方向連結リストも実現できる。これもどういう場合に使うんだろう。。
第6回
バイナリサーチツリー。ようやく実装方法が全然わからん奴が出てきた。
ツリーとは階層関係を表現するもの。数学的にはグラフの一種。ツリーはノードとエッジからなる。エッジはリンクと同じ。先頭ノードのことを節、vertexという。ツリーはベン図でも表現できる（！）。カッコでも表現できる（！）。例えばXMLもツリーだから、カッコとかベン図で書けるんだなあ。ノードのレベル（階層）はルートを0とする流儀と1とする流儀があるらしい。授業では0で定義。ノードが持つサブツリーのことを自由度という（なんで？）。
バイナリーツリーは子ノードの数を最大2個に制限したものをいう。日本語では二分木とか二進木とかいう。完全二分木は、最下層以外全部2個のノードをもっていて、かつレベルが全部同じ場合。で、バイナリサーチツリーは、左ノードの方が小さい、右ノードの方が小さい、というように配置したツリーのこと（別に完全二分木じゃなくていいみたい）。コード的には、左右ノードへのポインタを持っていればよい。
実装コード、左右に手動で挿入していくKUSOコードになっているが、挿入関数を作っていないからしょうがないか。
走査について。決まった規則で（全）ノードにアクセスすること。走査にもいろいろあって、行きがけ、通りがけ、帰りがけ走査がある（定義は略）。このうち通りがけ順操作は整列と同じ効果になる。どうにかしてバイナリサーチツリーを作ればソートできるってわけか。３つとも実装は簡単で、再帰呼び出しと出力の順番を変えるだけ。
最大値、最小値を求めること。簡単で、左ノードをたどれば最小値、右ノードをたどれば最大値になる。どちらもノード数が少なく、すぐ求められる。実装も楽勝。結局、バイナリサーチツリーを作るところが最大のポイントになるのでは？ノード数を数えるコードも簡単で、左右のノード数を再帰で数えて+1(自分の数)を返せばいい。ノード数は別にバイナリサーチツリーじゃなくてもよくて、ツリーなら何でも使えるね。高さを求めるコードも再帰で行ける。再帰ってかなり頭使うなぁ。
第7回
バイナリサーチツリーの操作について。探索と削除と挿入。探索は前回やったんじゃ？
探索はルートノードから値を比較して左右に辿っていけばOK。これは性質から明らかなんでそりゃそうだよね。ツリーにない値を探索しているかどうかは、末端まで行けばわかる。葉ノードまで到達しても値にヒットしなければ、該当なし。
挿入はまず探索から行う。葉ノードまで行ったら左右に挿入してやればいい。何もない場合からツリーを作るときは1番目のノードをルートにする。けど、これだと毎回ルートの取り方によって異なるツリーができない？どういうツリーにすれば効率的（レベルが浅くなる）になるんだろうね。
ノード削除について。削除は3通りの場合分けが必要になる。
- 葉ノードなら、単に消すだけでよい。
- 子ノードが1個ある場合、親ノードと子ノードを接続して自分は自滅する。
- 子ノードが2個ある場合。これが大変。inorder predecessor（順序内前任者、削除したい左側のサブツリーで最も右側にいるノード）を考える必要がある。通りがけ順走査では削除したいノードの一つ前のノード＝ソートした時一つ前に来るノードを、これから削除するノードの所に入れてやる。これで順序を保てるというわけ。うわーコード大変そう。もう一つのパターンとしては、inorder succesor(順序内後継者、削除したい右側のサブツリーで最も左側にあるノード＝ソート順で一つ少ないノード)を同様に、これから削除するノードの所に入れてもいい。それで削除ノードをdeleteする。これ、自分で思いつくかというと思いつかないなぁ。
コード例は印刷教材参照だって。そりゃそうだよなー。
バイナリサーチツリーの挿入順の話。整列してから挿入すると、単なる連結リストになりレベルが深くなってしまう。完全バイナリツリーだとツリーの高さはlog2(N+1)となり、高さに比べてノードをたくさん収納することができる。すると探索が楽。100万個でも高さはせいぜい20個。乱数を適当に挿入してもだいたいそうなる。ツリーの高さに計算量は比例するから、すべてO(logn)ということになる。ただ、形が悪いとO(n)になる。
じゃあいい感じの完全バイナリツリーに近いツリーを作るためにはどうするんだ、ってことが気になるけどそれは教えてもらえなかった。残念。ぱっと思いつくのは、だいたい中央に来る値からツリーに入れていけばいいんじゃないかってことくらいか。
第8回
ツリーの応用。平衡木とかいうのも説明するらしい。
まずはツリーの全ノード削除について。子が1-2個ある場合は削除が面倒なので、なるべく子が0個の場合（葉ノード）を削除したい。帰りがけ順走査をつかえばよい。コードとしては、左側にあるノードを優先して再帰で削除していくだけ。そうすると自動的に左側の葉ノードから消えてく。簡単！
メモリリークの話が出てきた。ちゃんと削除すればリークは起きないですねって言ってる（けど、最近の言語はみんなGCついてますよ！）
パス表示。すべてのパスを表示するためには、葉ノードを網羅してそこまでのパスを求めればよい。というわけで再帰的にノードを辿り、葉についた時点でパスを表示するとよい。
左右のノード反転。これも再帰的に左右反転関数を実行しまくるだけで終わり。コード短いでしょ！？って言ってる。
ツリーの高さの計算。サブツリーの高さを比較して+1して返す、これを再帰。この授業は再帰を勉強する科目なのかもしれない。
平衡木。やっと本丸に来た。葉ノードまでの高さをなるべく同じにするツリーのこと。AVLツリー、レッド・ブラックツリー、スプレイツリー、AAツリーなどいろいろあるらしい。ここではAVLツリーを見る。AVLツリーは、左右のノードの高さの差が必ず1以内になるらしい（どうやってやるんだ？）。
基本的に挿入・削除方法はバイナリサーチツリーとやり方は同じだが、挿入・削除後の処理が大変。でも見ていってくれるらしい。ルートからみて、高さが低いツリー、高さが高いツリーに挿入する場合、さらに高い方のツリーの左右のどちらに挿入するか、の場合分けが必要（以降は印刷教材を参照らしい。残念）。
実例。データ数を増やしていくと、ランダムの場合と高さがだいぶ違う。AVLツリーはランダムの場合の半分以下の高さになっているように見える。速度はAVLツリーの方が若干遅いがそこまでではない。ほぼランダムと同じ。でも計算量はlognに保たれる。いい感じのアルゴリズムだ。でも後処理が面倒らしい。実際どうなのか印刷教材が楽しみ。
第9回
ハッシュテーブルとオープンアドレスの話。
ハッシュ法は定数時間で速い。最速。本当なの！？そういえば配列のサイズとかってどうなってるんだろ。要はキーから算出したハッシュ値を配列に割り振ればいいんだよな。キーからの狭い配列に対する写像って感じ？ハッシュテーブルの配列数はバケットというらしい。
具体的なハッシュ関数について。ハッシュは切り刻むということ。一番簡単なのはmod。でもこれ10で割るんだったら、10までの配列にしか使えないよね？
ハッシュ値は衝突する。まず起こりにくくするには、配列を大きくしたり、演算を工夫したりする。演算の工夫、中央積算法。二乗して真ん中の方の値（6桁なら3-5桁目とか）をハッシュ値にする。折り畳み法。数字を分割して足し算して上から二桁とか必要な桁を取り出す。どっちにしても結局衝突は起きると思うけど。。？
衝突したらどうするか。その時の手段の一つがオープンアドレス法。空いてる配列を探すやり方のこと。具体的なやり方にはまず線形探索がある。+1していって空きを探す。簡単だが空きが連続して埋まるクラスターが発生してしまう。すると負荷がかかりやすい。
平方探索。再ハッシュ回数の定数倍とか再ハッシュ回数の2乗の定数倍とかを足して空きを探す。いい感じに見えるが、どれも同じ間隔の位置を探しちゃうから、セカンダリークラスタが発生する。
ダブルハッシング。ハッシュ関数を2つ用意し、片方は必ず足す、片方は再ハッシュ回数で掛ける。用意するハッシュ関数も工夫する。探査間隔が毎回変わるので、クラスタリングが避けられるというわけ。
ハッシュテーブルを実際に動かしてみる。データ数1億で、バケット数は2億、1.5億、1.1億とすると、1.1億は衝突がおきまくって遅いはず。実際、2.3倍くらいの速度差があった（思ったほどではない）。バイナリサーチツリー(o(logn))と比べるとすっごく高速。20倍速くらい。ただしメモリを食う。
第10回
ハッシュテーブルと連鎖法について。連鎖法とはハッシュテーブルの衝突解決のための手法の1つ。同一ハッシュ内のデータは連結リストにしてやればいいってわけ。（たぶん）メモリの使用量がかなり少なくなるが、衝突があると計算量は連結リストの計算量と等しくなるので、O(1)ではなくなるという欠点がある。
実装としては、ハッシュテーブル自体を連結リストの配列として実装する。で、ハッシュ値を格納するときに連結リストのノードを毎回確保して挿入していく。
実際計算量はどうなるのか。連結リストの長さL = データ数 / バケット数を考えると、計算量はO(1) + O(L/2) となる。バケット数が少ないほど、衝突が起きやすくなるので計算量はO(L)に近づく。バケット数と計算の速さはトレードオフというわけか。計算してみると、バケット数を1/100にすると、10倍の時間がかかった。
実装例、ハッシュテーブルの挿入に成功しているとなぜかエラーを返しているんだけどミス？
文字列データをハッシュテーブルのキーにする場合。まずK&R法。データをASCIIコードに変換してから全部足し算して、バケットの数で割り算すればハッシュ値になるというわけ。K&R本に載ってるんだってさー。djb法。左ビットシフトしながら足す（詳細はよくわからん）。ビットシフトがあるので、ハッシュ値はかなりでかい値になる。
コンピュータのメモリはだいぶ大きくなった（40年で100万倍）。なぜか光るメモリの紹介をされた。メモリが増えたのでハッシュテーブルで少々メモリを食っても速度の恩恵の方がでかいというわけ。
ハッシュ関数の応用として電子署名や改竄チェックのMD5、SHAなどがある。ほんの少しの改竄でもMD5は全然違う値になるので簡単にチェックができる。
ハッシュタグとは。# のことを井桁（いげた）記号とよぶ。米国ではナンバーサイン、パウンドサイン、欧州ではハッシュと呼ぶらしい。データ構造のハッシュとは関係ない（そうだったんか）。
第11回
再帰について。再帰と言えばマトリョーシカ人形。机に人形置いたまんま先生が話進めてる。
再帰コードは自分自身を呼び出して、毎回異なる（たしかに）引数を渡していくのが特徴。
簡単な例が階乗。20の階乗で243京になるらしい。コードは5行で終わり。ほぼほぼ return n * factorial(n-1); だけだしね。
再帰のコードは、まずwinding（再帰呼び出しが続くこと）が続き、terminate condition（終了条件）を満たしたら、、unwinding（もとの場所に戻っていくこと）の処理が行われて終わる、という捉え方をする。
フィボナッチ数。実質 return fibonacchi(n-1) + fibonacchi(n-2); だけ。再帰が2種類あるところがポイント。この再帰関数は廃棄されている計算結果が多く、無駄が多い。fibonacchi(30)を計算すると、400万回の関数コールが行われるらしい。じゃあどうやって効率化すればいいのかは示されなかった。
ユークリッドの互除法。本体は return gcd(y, x%y)); のみ。これはx, yの大小関係が考慮されてないけど大丈夫なんだろうか？
フラクタル図形への応用。フラクタル図形は自己相似になっているので再帰と相性が良い。POV-Rayというソフトが使いやすいらしい。例としてシェルピンスキー三角形をあげる。中点を結んだ正三角形をどんどん取り除いていくときれいな図形ができる。三次元のテトリックス図形というのもある。3Dでもそんなにコードの行数がいらない。メンガーのスポンジというのもある。同じことを立方体とか正方形でやればいい。
再帰とスタックについて。スタックを使うと再帰処理と同等の処理を扱うことができる。メモリが少ない時代はよく使われた。再帰は簡潔で数学的な記述もできるが、トレース（っていうかデバッグ）が難しい。バイナリサーチツリーの例をスタックにしてくれたがわかりづらい。コード量が増えたことだけがわかった。速度はどうなのか？
末尾再帰。実行する最後のステップが再帰になっていること。これをfor文に変えてやると、いろいろと節約できる。ちょっと例が分かりにくかったので、印刷教材で要復習。
第12回
ソーティングについて。さんざん他の講義でやったことだから、飛ばし気味に差分だけ学んでいこう。
ソートをやるためには必ず大小関係がないといけない。大小関係さえあれば昇順降順で並べ替えられる。
ソート前と同じキーの順序を変えない、安定ソートを実装するにはどうするのか。この講義では言及されず。バブルソート、挿入ソートは安定らしい。選択ソートは不安定。原理上安定になるかどうかで判定するしかないのか。
バブルソート10万件。O(n^2)だし時間かかるはず。12秒。厳しいね。ループ内がソート済みならなにもしない、という改良版バブルソートだと50%整列済みの配列を使って10.1秒。メモリ移動のコストを省くと2割くらいは速くなるのね。95%整列済みだと5秒。
選択ソート10万件は2.8秒。バブルソートよりはだいぶ速い。バブルソートはswapの回数が多いから遅いらしい。やはりメモリ内移動のコストはでかい。ただ、不安定ソートなのが悩みどころ。
挿入ソート、コード見ても何もわからん。困った。整列済みだと非常に速いのが特徴らしい。10万件でやはり2.73秒と速い。選択ソート並み。50%整列済みだと2.0秒、95%整列済みで0.262秒。とてもはやい。
古いPCと新しいPCでのソート時間の比較。先生の趣味のコーナーだな。99年のCeleron 300MHz vs 2017年のCore i7 2.8MHzを対決する。バブルソート10万件をおこなうと99年で315秒、2017年で15秒。22倍の差があった。ここで99年PCでクイックソートを行うと0.110秒。2017年PCよりずっとはやい。アルゴリズムによってこんなに差が出るのか。なお2017年PCでクイックソートをやると0.006秒。
第13回
ソートの応用。また他でやったアルゴリズムなので飛ばし気味で。
クイックソートは1960年にはもう作成されていたらしい。ホーア卿とか言う人が発明した。イギリス発祥なのか。分割統治アルゴリズムともいわれる。C言語のqsortはクイックソートの改良版（？）らしい。具体的にコード見てみたいね。クイックソート10万件の実験、0.009秒。はやい。1億件でも10秒で行ける。
クイックソートを2回行うこと。2回目は整列済み配列をさらにソートすることになる。どのような速度になるか。1回目は一瞬で終わるが、2回目は18.9秒。あれ、整列済みだと弱いのか？？なんで？？？理由としては、ピボットの選択手法によっては再帰の深さがめっちゃ深くなってしまうかららしい。というわけで、ピボットの選択方法によって対策をすれば整列済みデータでも全然速くなる。
再帰ではなくスタック利用のクイックソートについて。メモリが少ない環境では利用価値がある。大変な感じのソースになるが印刷教材に載ってるのかな。
C言語のqsortを使うとソート済みでも30万件→0.01秒で終わる（未整列よりはやい）。
マージソート。まず配列を分割し、少しずつマージしていく。実装としては、マージ用の配列と同じ要領のtemp領域が必要なのが特徴。1億件も13秒で終わる。たぶん、配列の分割がlog回で済むからだろう。利点は配列の整列未整列に依存しないこと。安定ソートであること。欠点は、メモリコピーのせいで若干パフォーマンスが落ちること。実測でもクイックソート比で3割遅い。結局、実用ではクイックソート改良版が最強ということになる。
第14回
ヒープの話。ヒープとは、ツリーに基づくデータ構造のこと。ノードの挿入と削除を高速に行える。完全二分木である。葉の高さが同じか、左＞右になっているもの。なんか今回先生飛ばしてるな。
最大ヒープ。親ノードの値が子ノードより大きいか等しいもの。最小ヒープもある。他にはフィボナッチヒープ、d-aryヒープなど。普通はバイナリヒープ（二分木のみ）を指す。
ノード挿入。まず最下段に追加、次にヒープ条件（最大とか）に従って値の交換を行う。ヒープ条件を満たしてなければ上段のノードと交換しまくっていけばいい。この時の計算量はo(logn)になる。交換の可能性は1/2と仮定できるので、正確には0.5 * logn。葉が多いから行える操作だ。
ノード削除。ルートノード削除を例にすると、まず葉ノードとルートノードを交換する。その後挿入と同じで、上から下に向かって交換を行っていけばいい。この際、どっちの子ノードと交換するかについての条件は不明。計算量はやっぱりo(logn)になる。
実際の実装では配列で行う。ルートが配列の1番目、レベル1が2,3番目、レベル2が4,5,6,7番目…などのように実装していけばいい。ダイレクトアクセスも可能にある。添え字kの左の子ノードは2k、右は2k+1、親ノードはk/2(切り捨て)で表現できる。なるほど！！添え字0からスタートでももちろんできて、左を2k+1、右を2k+2、親を(k-1)/2でやればいい。でも1からスタートした方がコストが少ないので、だいたいは1からスタートで実装しているらしい。
ヒープを利用したアルゴリズムの実装。まずは優先度付きキュー。ヒープで実装すればどれもo(logn)でいける。どうやって実装しているかは謎。印刷教材を見よってとこか。最大ヒープを使ってキューをenqueueの度に並べ替えれば、優先度の高い順に勝手に並べ替えられるってことなのかな。
ヒープソート。まず全部データをヒープに挿入して、ルートから最大値を取り出し（削除するってことか？）ヒープを再構成しながら挿入済み配列にデータを移していく。計算量はo(logn)が2回分。クイックソートよりはこの2回が効いてきて若干遅いが、整列済みかどうかに影響を受けない。あと、クイックソートと同じく不安定ソートであるのが欠点。10万件で0.009秒、1億件で82秒。クイックソートよりけっこうかかる（コードが適当だからかもだって）。
第15回
グラフの話。グラフとはノード同士をつなぎまくったデータ構造のこと。ツリーもグラフの一種である。
グラフ周りの用語について。頂点Vertex（ノード）と辺Edge（ポインタでリンクを張ることに相当）。辺の両端にある頂点は隣接しているという。ある頂点から別の頂点に至る連続する辺のことをパスという。パスは複数ありうる。
連結グラフと非連結グラフ。すべての頂点を行き来できれば連結で、分断されていれば非連結。輪になっていたら閉路グラフ。Cnと表記する。辺に方向性があるグラフを有向グラフという。
辺に重みをつけると重み付きグラフ。これはカーナビとか運賃でよく使う。完全グラフは全頂点間に辺があるもの。辺の数は計算できる。
コンピュータでどう表現するか。まず隣接リスト。a→b,c b→a,c c→a,b,d d→c みたいな感じ。有向グラフも重み付きグラフも表現可能。自己参照もOK。
隣接行列。辺があるかないかを二次元行列で表現。ちょっとテキストで書くのは無理。ピクロスみたいな感じ。容量が大きい。有向も行けるし重みは数字を大きくすればいいからいける。無向グラフなら三角行列で十分。
実装。行列の方が楽で探索時間も少ない。ただしメモリを食う。
グラフの密度について。密度が低いと隣接リストが、高いと隣接行列が有利。だいたいeの数がvの2乗に等しくなってくるとけっこう密度が高い。
コード例。ぜんぜんいみわからん。
グラフの探索。接続情報に基づいて全頂点をたどることをいう。まず深さ優先探索。頂点をたどって行って先に進めなくなったら後戻りする。未訪問の頂点を訪ねて、頂点をスタックにpush。進めなくなったらpop。C言語で300行くらいになる。大変。とりあえずスタック使うんだなってことだけがわかった。
幅優先探索。近くにある頂点を優先的に訪ねていく。キューで実装する。頂点に隣接する未訪問の頂点をenquere。未訪問の頂点がなければdequere。動作例を見て何となく意味は分かった。深さ優先探索より速そう。どういう欠点があるのかな。