Java优先级队列接口实现

Question

这几天前我在面试中被问到的问题,我不确定这种方法.建议将受到高度赞赏:

如何实现PriorityQueue接口以获取O(1)中的queue()方法和O(n)中的dequeue()方法.

如何实现PriorityQueue接口以获取O(n)中的queue()方法和O(1)中的dequeue()方法.

谢谢.

Answer 1

典型的PriorityQueue实现将使用Heap为"add"操作获得O(lg n)性能,因此O(n)性能将更加容易.

例如,您可以使用向量或链接列表作为基础数据结构.对于O(1)"添加",您可以简单地将新值添加到结尾,对于O(n)"删除",您可以对最小值进行线性搜索.相反,对于O(n)"add",你可以进行线性扫描以找到下一个最大值,然后在它之前插入,对于O(1)删除你可以简单地删除列表的第一个元素.