我遇到了这个问题: 实现一个队列,其中push_rear(),pop_front()和get_min()都是常量时间操作.
我最初想过使用一个最小堆数据结构,它对于get_min()具有O(1)复杂度.但是push_rear()和pop_front()将是O(log(n)).
有谁知道实现这样一个有O(1)push(),pop()和min()的队列的最佳方法是什么？
我搜索了这个,并想指出这个算法极客线程.但似乎没有一个解决方案遵循所有3种方法的恒定时间规则:push(),pop()和min().
感谢所有的建议.
这是数据结构的描述:
它的操作类似于带有get,put和remove方法的常规地图,但有一个sort方法可以调用以对地图进行排序.但是,映射会记住它的排序结构,因此后续的sort调用可以更快(如果结构在调用之间没有太大的变化sort).
例如:
put方法为1,000,000次.sort方法.put方法称为100次.sort方法.我第二次调用该sort方法应该是一个更快的操作,因为地图的结构没有太大变化.请注意,映射不必维护调用之间的排序顺序sort.
我明白,这也许是不可能的,但我希望为O(1) get,put和remove操作.像TreeMap这样的东西为这些操作提供了保证的O(log(n))时间成本,但始终保持排序顺序(无sort方法).
那么这个数据结构的设计是什么？
编辑1 - 返回前K个条目
虽然我很高兴听到上面一般情况的答案,但我的用例更加具体:我不需要对整个事情进行排序; 只是顶部的K元素.
谢谢!