我正在为面试练习这个问题。
将在最短的时间内实现以下 3 个操作的最佳数据结构：
a.) insertion.
b.) removing the oldest element.
c.) printing the largest element.
我能想到的最好的是最小/最大堆或优先级队列。对于操作 (a) 和 (c) ，堆是有效的，但我不确定，第二个操作“删除最旧的元素”可以使用堆有效地完成。
所以建议一个理想的数据结构，可以有效地实现所有 3 个操作。
谢谢！
问问题
472 次
2 回答
3
将某种最大堆用于操作a、c和一个额外的节点队列，按历史顺序存储它们怎么样？如果您使用Fibonacci Heap，您将获得操作a和c的O(1)时间，以及操作b的O(logN)时间。您只需在添加新元素时将指向新节点的指针推入队列，并在删除最旧元素时删除队列前面指向的节点（当然是从队列中弹出）。
于 2012-08-02T08:25:39.633 回答
1
我认为最老的他是指插入时间，而最大的元素是具有最高价值的元素。也许你可以把它写成 (value,insertiontimes) 的元组
也许您可以在最大堆中插入所有元素以获取值，并在几分钟内听到插入时间并连接它们。在我看来，有 2 个堆是连接的，而这些对是元组的表示。它不是很优雅，但它应该可以工作。每次插入和删除后，您需要检查堆属性。
于 2012-07-27T07:32:59.763 回答