懶惰插入/刪除

我有一個任務來編輯優先級隊列並實現（除其他外）插入函數。 Allthough我的書提到了「懶惰刪除」和其他懶惰行爲，它永遠不會指定「懶惰」實際上意味着什麼。懶惰插入/刪除

總之：插入/刪除函數和LAZY插入/刪除函數有什麼區別？

「懶東西」通常意味着「東西」儘可能延遲，只有在真正需要時纔會執行。 –

因此，例如在刪除的情況下，您可能只需將該項目標記爲/將其標記爲已刪除，並將其實際刪除的工作留到了更方便的時間。或者，您可能永遠不會真的刪除東西，但是當您需要插入時，只需將其位置視爲「可用空間」即可。 – jam

「懶惰刪除」通常意味着您標記刪除的內容而不是直接刪除它，並修改其他操作以假裝標記的項目不存在。

例如，在優先隊列的情況下，您可以在出列過程中跳過已刪除的項目，而不是主動從中間刪除它們，這更困難。

類似地，「延遲插入」可能會將元素添加到輸入隊列中，這是一個常量操作。通常，插入優先級隊列需要O（log n）時間。嘗試出隊時，輸入隊列將被刷新到優先級隊列中。這將具有卸載插入操作的成本直到出列操作的效果。

基本上「懶惰」的意思是不做一個操作，直到它的結果是必要的。

2012-10-17 14:14:14 Joni

謝謝你的答案！但這對懶惰插入意味着什麼？ –

查看更新的答案 – Joni

回答