O(1)で配列から最大値をゲットするには

みたいなことが飲み会で話題になった。

「やっぱヒープ」じゃない？

みたいな話に落ち着いた気がするんだけど、単純に最大値のインデックスを保持しとくのもありだなーと思ったので、土曜日だしなんとなく実装。

http://bitbucket.org/oza/algorithm/changeset/ee5949c52b99/

メイン処理でやっていることは全く難しくなくて、

初期化時に配列を走査して、最大値をインデックスを保持しておき、
最大値がほしいときにはその最大値のインデックスを使って値をとる

というだけ。

仮に配列が可変長になって、要素のaddやdeleteが必要になっても対応可能(未実装だけど...w)。pack構造体の中には最大値のインデックスが保持されているので、O(1)で追加することができる。ただし、deleteは重い。「2番目に大きな数」などは保持していないから、1番大きな数が消去されたりすると、線形探索が走ってO(n)のコストがかかってしまう。まぁ線形探索やめろって話だけどw

で、何が言いたかったかというと、大学の講義とかの課題で、「〜をO(1)で満たせるようなアルゴリズムを設計しなさい。状況は限定してよい」みたいな出題をすると、結構力つくんじゃないかなー、ということ。やっぱり自分で考えると身に付き方が違う。洗練してるうちにすごいのができるかもしれないし、講義を介して研究ネタができたらまさにwin-win。なんてことを妄想してました。ハイ。