c++ - 遅延挿入/削除

Question

プライオリティ キューを編集し、(とりわけ) 挿入機能を実装する割り当てを受けました。私の本では「遅延削除」やその他の遅延アクションについて言及していますが、「遅延」が実際に何を意味するのかは明記されていません。

要するに、挿入/削除関数とLAZY挿入/削除関数の違いは何ですか?

Answer 1

「遅延削除」とは、通常、何かを直接削除するのではなく、削除済みとしてマークし、他の操作を変更して、マークされたアイテムが存在しないふりをすることを意味します。

たとえば、プライオリティ キューの場合、削除されたアイテムを途中から積極的に削除するのではなく、デキュー プロシージャでジャンプすることができますが、これはより困難です。

同様に、「遅延挿入」は要素を入力キューに追加する場合がありますが、これは一定時間の操作です。通常、プライオリティ キューへの挿入には O(log n) の時間がかかります。デキューしようとすると、入力キューがプライオリティ キューにフラッシュされます。これは、デキュー操作までの挿入操作のコストをオフロードする効果があります。

基本的に「怠惰」とは、結果が必要になるまで操作を行わないことを意味します。