algorithm - 去旧打印最大的数据结构

Question

我正在为面试练习这个问题。

将在最短时间内实现以下 3 个操作的最佳数据结构::

a.) insertion.
b.) removing the oldest element.
c.) printing the largest element.

我能想到的最好的是最小/最大堆或优先级队列。对于操作 (a) 和 (c)，堆是有效的，但我不确定，第二个操作“删除最旧的元素”是否可以使用堆有效地完成。

因此建议一个理想的数据结构，该结构将有效地实现所有 3 个操作。

谢谢!

Answer 1

如何为操作a,c 使用某种最大堆以及一个额外的节点队列，以历史顺序存储它们？如果你使用 Fibonacci Heap ，您将获得 O(1) 操作时间 a 和 c，以及 O(logN) 时间对于 b。您只需要在添加新元素时将指向新节点的指针插入队列，并在删除最旧元素时删除队列前端指向的节点(当然是从队列中弹出)。