惰性插入/删除

Question

我得到了一个任务，要编辑一个优先级队列并实现一个插入函数(以及其他事情)。尽管我的书提到了“懒惰删除”和其他懒惰行为，但它从来没有具体说明“懒惰”实际上是什么意思。

简而言之:插入/删除函数和懒惰的插入/删除函数有什么区别？

Answer 1

“惰性删除”通常是指你标记已删除的东西，而不是直接删除它，然后修改其他操作来假装标记的项目不在那里。

例如，在优先级队列的情况下，您可以在出队过程中跳过已删除的项目，而不是从中间主动删除它们，这更难。

类似地，“惰性插入”可能会将元素添加到输入队列中，这是一个恒定时间的操作。通常，插入到优先级队列中需要O(log )时间。当尝试出队时，输入队列将被刷新到优先级队列中。这将具有卸载insert操作的成本直到出列操作的效果。

从根本上说，“懒惰”意味着在需要结果之前不做操作。