Java 优先级队列接口(interface)实现

Question

这是几天前我在面试中被问到的问题，我不确定这种方法。建议将不胜感激:

如何实现 PriorityQueue 接口(interface)以在 O(1) 中获取 queue() 方法并在 O(n) 中获取 dequeue() 方法。

如何实现 PriorityQueue 接口(interface)以在 O(n) 中获取 queue() 方法并在 O(1) 中获取 dequeue() 方法。

谢谢。

Answer 1

典型的 PriorityQueue 实现会使用堆来为“添加”操作获得 O(lg n) 性能，因此 O(n) 性能会更容易。

例如，您可以使用 vector 或链表作为底层数据结构。对于 O(1)“添加”，您可以简单地将新值添加到末尾，对于 O(n)“删除”，您可以对最小值进行线性搜索。相反，对于 O(n) 的“添加”，您可以进行线性扫描以找到下一个最大值，然后在它之前插入，对于 O(1) 的删除，您可以简单地删除列表的第一个元素。