<code>
<br>#ifndef __HEAPSORT_H__
<br>#define __HEAPSORT_H__
<br><br>template <typename t><br>void MaxHeapify( T* target, unsigned int index , unsigned int length) {
<br>	unsigned int l = index	unsigned int r = (index	unsigned int max = index;
<br>	if( l 		max = l;
<br>	}
<br>	if( r 		max = r;
<br>	}
<br>	if( index != max ){
<br>		T tmp = target[index];
<br>		target[index] = target[max];
<br>		target[max] = tmp;
<br>		MaxHeapify( target, max, length );	
<br>	}
<br><br>	return;
<br>}
<br><br>template <typename t><br>void BuildMaxHeap( T* target, unsigned int length ){
<br>	for( unsigned int i = (length-1)/2; true ; i-- ){
<br>		MaxHeapify( target, i, length );
<br>		if( 0 == i ){
<br>			break;
<br>		}
<br>	}
<br>}
<br><br><br>template <typename t><br>void HeapSort( T* target, unsigned int length){
<br>	BuildMaxHeap( target , length );
<br>	while(length != 0 ){
<br>		T tmp = target[length-1]; 
<br>		target[length-1] = target[0];
<br>		target[0] = tmp;
<br>		length--;
<br>		MaxHeapify(target, 0, length );
<br>	}
<br>}
<br><br>#endif
<br><br><br></typename></typename></typename></code>

includeしてから次ように使う。

<code>
<br>unsigned char buf[] = {5,7,10,8,11};
<br>HeapSort( buf, 5 );
<br>//ここでbuf内はソート済み。
<br></code>

まあ、そんなことを言っていてもどうもならないし、病院に行ってはいるので、そこで言われるようにするしかないということで、勉強をしようと思って、本なりビデオなりを見ている。

そんなとき、以前にFacebookの採用情報欄にパズルが載っていたのを思い出した。プログラミングの問題が載っていて、それを解いて送ると、まあ、採用に少しは考慮してくれるみたいな感じのやつ。
ただし、結構難しい。

というわけで、今回はこれをやってみることにした。
http://www.facebook.com/careers/puzzles.php#!/careers/puzzles.php?puzzle_id=8
Peak Trafficという問題。

いろいろアルゴリズムなどを調べながらやった。
今回はちょっと１日当たりパソコンを触っていられる時間も限られているので、２週間ぐらいかけてちょっとづつ調べたり、プログラム書いたりして完成させた。

Facebookにこのトピックに関しての掲示板があったのでそこも参考にした。すでに解いている人が、テスト用データやどのくらい処理に時間がかかったかなどを載せている。
http://www.facebook.com/careers/puzzles.php#!/topic.php?uid=15325934266&topic=6943

とりあえず、今日Facebookに送ったところ、正解とのこと。扱ったことのないデータ構造やアルゴリズムだったのでそれだけでもかなり勉強になった。

ただ、何日か前に一応答えを出せるプログラムは書いたのだけれど遅いのが気になって少し何とかならないかと挑戦したけど、だめだった。
さっきの掲示板に投稿している人は、あるテストデータ（60MB程度）を処理するのにPythonで書いて、10秒以内だそうだ。ちなみに僕のはRubyで書いて6分；；。お話になりません。

どうしたらいいんだろうと考えたけど、だめだった。まだまだ考えられる余地はあるので、まだがんばる。
PythonとRubyの差も多少はありそうだが、そんなレベルの違いじゃないな。

ちなみに、そんなときに出会ったのが以下のレクチャー
（これ自体はこのとはの直接の答えではないけど、何か得られるものがないかと思って見た。）
この前のMITの授業といい、こんなのが見られるなんて何て素晴らしいんだ。
ほかにもUCBerkleyのStructure and Interpretation of Computer Programを使った授業もYouTubeで見られる。
この辺は、どこかのページにテキストブックとともにまとめておく価値がありそうだ。

うーん、すばらしい。勢い余って線形代数も受講

これまたすばらしい。英語なのに大学の時に受けた授業より分かりやすいってどういうことだ。まあ、まだ簡単な内容だからかもしれないけど。

これからも続けて受けていきたい。