最小ヒープでの挿入/削除の償却コスト
最近、面接の質問に出くわしました。追加情報は問題になりません（おそらくデフォルトの実装を使用する必要があります...）
空の最小ヒープ（削除要素の場所がわかっている）での挿入および削除操作の任意のシーケンスには、次のコストが償却されます。
A）O（1）を挿入し、O（log n）を削除します
B）O（log n）を挿入し、O（1）を削除します
オプション（B）は正しいです。
解答用紙を見てびっくりしました。これはトリッキーで、おそらく空のヒープであり、削除する要素の場所を知っているかもしれません...なぜ（A）が間違っているのかわかりませんか？なぜ（B）が正しいのですか？
回答
データ構造の操作に償却原価を割り当てるときは、実行される操作のシーケンスについて、償却原価の合計が常に少なくともそれらの操作の実際のコストの合計と同じになるようにする必要があります。
それでは、オプション1を取り上げましょう。これは、O（1）の償却原価を挿入に割り当て、O（log n）の償却原価を削除に割り当てます。私たちが聞いている質問は以下の通りである：それは事実であるいずれかのために、空のバイナリヒープ上の一連の操作、これらの操作の実際のコストは、これらの操作の償却原価で上位囲まれていますか？そしてこの場合、答えはノーです。ヒープへの純粋なn回の挿入のシーケンスを実行するとします。これらの操作を実行するための実際のコストは、各要素がヒープの最上部までバブルする必要がある場合、Θ（n log n）になる可能性があります。ただし、n回の操作を実行し、それぞれがO（1）時間かかると偽ったため、この会計スキームでは、これらの操作の償却コストはO（n）になります。したがって、この償却会計スキームは、私たちが行っている作業を過小評価する可能性があるため、機能しません。
一方、オプション2を見てみましょう。ここでは、O（log n）を償却挿入コストとして割り当て、O（1）を償却除去コストとして割り当てています。さて、これらの操作の実際のコストが償却コストを超えるn個の操作のシーケンスを見つけることができますか？この場合、答えはノーです。これを確認する1つの方法があります。挿入の償却コストをO（log n）に設定しました。これは実際のコストと一致するため、合計を過小評価する唯一の方法は、削除の償却コスト（O（1））を使用することです。 ）、これは削除の実際のコストよりも低くなります。ただし、ここでは問題ありません。削除操作を実行できるようにするには、削除する要素を事前に挿入しておく必要があります。挿入と削除の合計実コストはO（log n）+ O（log n）= O（log n）であり、挿入と削除の合計償却コストはO（log n）+ O（1 ）= O（log n）。その意味で、削除が速いふりをしても、全体的なコストは変わりません。
2番目のアプローチが機能する理由を直感的に理解するための優れた方法ですが、最初のアプローチは機能しません。これは、償却分析のすべてについて考えることです。償却の背後にある直感は、将来の操作にかかる時間が短くなるように、以前の操作にもう少し課金することです。2番目のアカウンティングスキームの場合、まさにそれが私たちが行っていることです。バイナリヒープから要素を削除するコストを、最初にその要素をヒープに挿入するコストに戻します。このように、作業を後方にシフトするだけなので、償却原価の合計を実際の原価の合計より低くすることはできません。一方、最初のケースでは、我々は仕事をシフトしている前方の挿入のための欠失の賃金を作ることによって、時間に。しかし、それは問題です。なぜなら、大量の挿入を行った後、対応する削除を行わない場合、作業は存在しない操作にシフトするからです。
ヒープは最初は空であるため、挿入よりも多くの削除を行うことはできません。
削除ごとのO（1）と挿入ごとのO（log N）の償却コストは、挿入と削除の両方のO（log N）の償却コストとまったく同じです。これは、削除コストをカウントするだけでよいためです。対応するインサート。
それは逆には機能しません。削除よりも多くの挿入を行うことができるため、各挿入のコストを支払うのに十分な削除がない可能性があります。