Nik*_*chi 9 heap performance complexity-theory priority-queue
我正在使用优先级队列,该队列最初将其元素的优先级基于启发式算法.当元素出列时,启发式更新,并且队列中当前的元素可能会增加其键.
我知道有堆(特别是Fibonacci堆)已经摊销O(1)减少了关键操作,但是有没有任何堆结构在增加键操作上有类似的界限？
对于我的应用程序来说,这远远不是一个性能问题(二进制堆工作正常)它真的只是学术上的好奇心.
编辑:澄清一下,我正在寻找一个数据结构,它具有比O(logn)时间更快的增加键操作,而不是减少键.我的应用程序永远不会减少密钥,因为启发式过度估计优先级.
| 归档时间： |
|
| 查看次数： |
3402 次 |
| 最近记录： |