我正在使用一个优先级队列,它最初将其元素的优先级基于启发式。随着元素出列,启发式方法会更新,并且当前队列中的元素可能会增加其键。
我知道有些堆(特别是斐波那契堆)已经摊销了 O(1) 减少键操作,但是是否有任何堆结构在增加键操作上有类似的界限?
对于我的应用程序,这远非性能问题(二进制堆工作正常),这实际上只是学术好奇心。
编辑:澄清一下,我正在寻找一种数据结构,其增加键操作的时间比 O(logn) 快,而不是减少键。我的应用程序从不减少密钥,因为启发式高估了优先级。
我正在使用一个优先级队列,它最初将其元素的优先级基于启发式。随着元素出列,启发式方法会更新,并且当前队列中的元素可能会增加其键。
我知道有些堆(特别是斐波那契堆)已经摊销了 O(1) 减少键操作,但是是否有任何堆结构在增加键操作上有类似的界限?
对于我的应用程序,这远非性能问题(二进制堆工作正常),这实际上只是学术好奇心。
编辑:澄清一下,我正在寻找一种数据结构,其增加键操作的时间比 O(logn) 快,而不是减少键。我的应用程序从不减少密钥,因为启发式高估了优先级。