max_queue 最大値をいち早く返すデータ構造 - くまメモちょっとマニアックなデータ構造を紹介 その名もmax queue、使い勝手はほとんどFIFOなqueueと一緒で、enqueue()もdequeue()もO(1)だけどそれに加えて「入ってるデータのうち最大の値」もO(1)の計算量で算出するという代物。 兄弟分で最小の物を返すmin queueや、両方の機能を備えたmin-max queueもあるけどmax queueが判れば自明なので割愛。 最大の値を覚えておけば良いだけに思えるけど、最大の値がdequeueされてしまった場合にO(n)の時間を掛けて再び探索してたら条件を満たせない。 max-queueでは最大の値を覚えておくため専用のqueue（以後最大値queueと呼ぶ）を内部でもう一本持つ。 この青い線がqueueに入ってるデータ列で高さがデータの大きさを表す、下に書かれている薄い線の入ったデータ列が最大値queue。 こちらの最大
BLOGOS サービス終了のお知らせ
