懒惰插入/删除

我有一个任务来编辑优先级队列并实现（除其他外）插入函数。 Allthough我的书提到了“懒惰删除”和其他懒惰行为，它永远不会指定“懒惰”实际上意味着什么。懒惰插入/删除

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

“懒东西”通常意味着“东西”尽可能延迟，只有在真正需要时才会执行。 –

因此，例如在删除的情况下，您可能只需将该项目标记为/将其标记为已删除，并将其实际删除的工作留到了更方便的时间。或者，您可能永远不会真的删除东西，但是当您需要插入时，只需将其位置视为“可用空间”即可。 – jam

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

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

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

基本上“懒惰”的意思是不做一个操作，直到它的结果是必要的。

2012-10-17 14:14:14 Joni

谢谢你的答案！但这对懒惰插入意味着什么？ –

查看更新的答案 – Joni

回答