次のアルゴリズムの問題を解決しようとしています。
要素を挿入し、最小要素を削除して書き込むことができるデータ構造があるとしましょう。そして、一連のコマンドを知っていると仮定しましょうn。それらはすべてI(k)(k を挿入) またはD(最小値を削除して出力) のいずれかです。
私たちの仕事は、各Dコマンドが返す数値を決定することです。たとえば、シーケンスの場合:
I(2) D I(5) I(4) I(3) D D I(1) D D
結果は
2 3 4 1 5
目標 (またはヒント) は、複雑さよりも優れたものを達成することです。これにより、 でセットの作成、検索、結合O(nlog(n))を行うことができる Find-Union データ構造を使用します。ここで、 は逆アッカーマン関数です。nO(na(n))a(n)
これは宿題ではありません - 私は試験の準備をしていて、すでに数時間以上この演習に苦労しています.
さらなるヒントをいただければ幸いです
編集：重要な仮定を1つ追加するのを忘れていました。挿入するすべての数値は範囲 1..n からのものです
さらに編集：その問題に遭遇したのは私が最初ではないことがわかりました。これはオフライン最小問題と呼ばれ、興味のある人はここでさらに読むことができます