アルゴリズムとデータ構造 宿題 (ヒープ)

概要説明:
ヒープ(半順序木による優先度待ち行列の実現)を「自分で」実装してみて、n個insertしてからn個deleteminした場合の実行時間を計測し、実際に O( n log n )であることを確認してみる。 プログラミング言語や実行環境は何を利用してもよいが自分でゼロから書いてみること。 どうしてもデバッグが終わらなかった場合には、その旨を記して、途中の段階のコードを〆切前に提出すること。 また、他学科の学生などでどうしても実装できない場合にはネットから探してきて動かしてもよいが、その場合にはその旨を明記すること。

提出方法:
以下のgoogle フォーム ( http://goo.gl/forms/9io49dO19u ) に回答すること。複数回提出された場合には、最新のものを受理する。

締切:
2015年11月8日(日)深夜24:00 厳守

初心者向け:
プログラミングの経験がない学生のために javascript によるサンプル ( sample_heap.html ) を用意した。 ページをローカルに保存して、テキストエディタ(メモ帳など)で開けばソースコードを見て編集できる。それをブラウザで開けば実行できる。 この中の insert, deletemin の部分を実装すればよい。文法などは「javascript 入門」などで検索すればいろいろ出てくる。

経験者向け:
できればjavascriptよりは CやJavaなどで実装してみることを勧める。また、ヒープの実装はあくまでも最低限の練習なので、他のアルゴリズムについても実装して速度を測ってみることを強く勧める。

連絡先:
質問などがあれば五十嵐まで ( takeo@acm.org )。