n 要素セットで次の操作をサポートするデータ構造を考案します。
O(lg n)O(1)ます。delete max はO(lg n)従来のヒープを使用することに注意してください。私のアプローチ：
ルート (最大ヒープ内の最大値) を追い越す潜在的な後継者を追跡する別の配列を保持することにしました。一度削除されます。したがって、最大値を削除すると、そのうちO(1)に配列を調べて、次の適切な後継者を見つけます（これはインテリジェントに設定したと思います）。
誰もがより良いアプローチを持っていますか? ヒープの使用に固執するようにしてください。これは宿題の質問ではありません。私は面接の準備をしています。それは Skiena の本からです。
要件は非常に具体的です。関心があるのは、insert O（lg n）とdeleteMin O（1）の2つの操作だけです。
既知のヒープ構造はどれも、特定の制約を満たしていません。代わりに、最良の構造（理論的には-銀河構造と呼ばれることもあります）はBrodal Queueです。これは、 O（lg n）を最悪にするdeleteMinを除いて、 O （1）最悪の場合にすべてのヒープ操作を実行します。-ケースタイム。他のすべての既知の構造は良くありません。
これらの2つの操作のみに関心があるため、これら2つの操作のみを適切に処理するカスタム構造を使用することができる場合があります。これは、キーの削減、マージなどについて心配する必要がないためです。一般的なヒープ構造については心配する必要があります。
以下を含む二重構造DLの維持：
さらに、 Lの各エントリとDまたはTの対応するエントリの間のリンクを維持し、その逆も同様です。さらに、 Dのエントリごとに、 Lで削除されたかどうかを示すビットを維持する必要があります。後でDとLの間で一括同期を行うために、最後の同期以降のLからの削除の数dを追跡することもできます。次の不変条件の後に同期を行うことができます。
違反しています。そうすれば、同期時間はnで線形のままであり、常に|を保証できます。T | およびdは管理可能な範囲内です。
したがって、新しい要素eをDLに挿入するには、最初にDでその後続（先行）のfind（e）を実行し、別のTで後続を検索して、より大きな後続（より小さな先行）の参照を取得し、それを使用します。Lに挿入し、 eをTに追加して、参照を維持します。eを挿入した後、不変条件1に違反していないかどうかを確認します。その場合、同期をトリガーします。
同期は基本的にTとDの内容をマージし、削除済みとしてマークされた要素を新しいD構造に削除します。これは、|T|で時間線形に実行できます。+ | D | = O（n）。別の線形時間では、LとDの間の参照を更新できます。この一括同期のコストは、挿入と削除に分配（償却）できます。このため、これらの費用は償却費のみです。
deleteMinを実行するには、Lの先頭を削除し、 Dへの後方リンクを使用して、 Dの対応するエントリを削除済みとしてマークし、dをインクリメントします。
観察1 ： Lは常に最新であるため、deleteMinは常に最小要素を削除することに注意してください。
観察2：Dは常にLと同期しているわけではありません。いくつかの削除された要素（そのようにマークされている）といくつかの挿入された要素がTでのみ見つかる可能性があります。
観察2までに、 O（lg n）の検索と挿入のコストを維持するために、ある時点でDとLの同期をスケジュールする必要があります。これは、不変条件1に違反するたびに実行されます。
私がちょっとおおざっぱに言った厄介な問題の1つは、次のとおりです。同期中に線形スキャンを実行できる一方で、対数時間でTに挿入するにはどうすればよいですか。ある種のバランスの取れた木だけがこれを達成することができます。Tのサイズを対数サイズに制限するというアイデアを少しいじってみましたが、同期をトリガーするのに十分な数の挿入が行われると、同期の償却コストが増加します。ある種のスレッド化されたバランスの取れたツリーまたはスキップリストでさえ、ここで役立つはずです。
ここですべてのアサーションを証明または実装したわけではないので、自由に批評して改善を提案してください。
更新：@delnanが指摘しているように、これらの費用は償却されます。この事実を強調するために説明を更新し、わかりやすくするために改訂しました。おそらく、いくつかのトリックで償却を削除することができますが、その場合は別の銀河構造になります。
スキップ リストを使用することをお勧めします。これは、要求された複雑さでこの操作をサポートする、私が考えることができる最も簡単なデータ構造を実装するためです。フィボナッチ ヒープも機能しますが、実装は非常に困難です。
編集: フィボナッチ ヒープの言葉を元に戻します - 定数の挿入とO(log(n))削除をサポートしています。これは、必要なものとは逆です。そのために残念。