我有一项任务是编辑优先级队列并实现(除其他事项外)插入功能。尽管我的书提到了“懒惰删除”和其他懒惰操作,但它从未具体说明“懒惰”的实际含义。
简而言之: 插入/删除函数和 LAZY 插入/删除函数有什么区别?
最佳答案
“惰性删除”通常是指标记删除的内容而不是直接删除它,并修改其他操作以假装标记的项不存在。
例如,在优先队列的情况下,您可以跳过出队过程中已删除的项目,而不是主动从中间删除它们,这更难。
类似地,“惰性插入”可能会将元素添加到输入队列中,这是一个常量时间操作。通常插入优先级队列需要 O(log n) 时间。尝试出列时,输入队列将被刷新到优先级队列中。这将具有减轻插入操作成本直到出列操作的效果。
基本上“惰性”意味着直到需要结果时才进行操作。
关于c++ - 延迟插入/删除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12936195/