c++ - 延迟插入/删除

Question

我的任务是编辑优先级队列并实现（除其他外）插入功能。尽管我的书提到了“延迟删除”和其他延迟操作，但它从未指定“延迟”的实际含义。

简而言之：插入/删除函数和 LAZY 插入/删除函数有什么区别？

Answer 1

“懒惰删除”通常意味着您将某些内容标记为已删除而不是直接删除它，并修改其他操作以假装标记的项目不存在。

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

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

基本上“懒惰”意味着在需要结果之前不进行操作。