queue - 在 O(1) 时间内支持最小、最大操作的队列的正确数据结构是什么？

Question

支持入队、出队、峰值、最小和最大操作并在 O(1) 时间内执行所有这些操作的队列的正确数据结构是什么？

最明显的数据结构是链表，但最小、最大操作将是 O(n)。 Priority Queue 是另一个完美的选择，但 Enqueue、Dequeue 应该以 Queue 的正常方式工作。 (先进先出)

想到的另一个选项是堆，但我无法弄清楚如何使用堆设计具有最小、最大操作的队列。

任何帮助深表感谢。

Answer 1

如果 min() 和 max() 实际更改了结构，则无法设计您寻求的数据结构。如果 min() 和 max() 与 peek() 类似，并且提供只读访问权限，那么您应该按照 this question 中的步骤进行操作。 ，添加另一个类似于用于 max() 操作的 min() 操作的双端队列。这个答案的其余部分假设 min() 和 max() 实际上 删除 相应的元素。

由于您需要 enqueue() 和 dequeue()，因此必须按到达顺序 (FIFO) 添加和删除元素。一个简单的双端队列(链接或使用循环向量)将在 O(1) 中提供。

但是要添加的元素可能会改变当前的 min() 和 max()；然而，当删除时，旧的 min() 和 max() 值应该被恢复......除非它们在此期间被删除。此限制迫使您以某种方式对元素进行排序。任何排序结构(最小堆、最大堆、平衡二叉树等)至少需要 O(log n) 才能找到新到达的位置。

最好的办法是将平衡二叉树(对于 min() 和 max())与双向链表配对。您的树节点将存储一组指向列表节点的指针，按您在 min() 和 max() 中使用的任何键排序。在 Java 中:

// N your node class; can return K, comparable, used for min() and max() 
LinkedList<N> list;           // sorted by arrival
TreeMap<K,HashMap<N>> tree;   // sorted by K

在 enque (), 你会在 list 的末尾添加一个新节点，并通过其键将该节点添加到 HashMap在其节点中 tree . O(log n)。

在 出队 ()，您将从 list 的开头删除节点，并从其树中节点中的 HashMap 。 O(log n)。

在 分钟 ()，您将查找树中的第一个元素。 O(1)。如果你需要删除它，你有指向链表的指针，所以 O(1) 在那一边；但是如果它是具有该特定 K 的最后一个元素，则 O(log n) 重新平衡树。

在 最大 ()，同样的逻辑适用；除了您要查找树中的最后一个元素。所以 O(log n)。

在 偷看 ()，查看但不提取队列中的第一个元素将是 O(1)。

如果您知道所有键都是唯一的，则可以简化此操作(通过删除 HashMap)。但是，这不会影响渐近成本:它们都将保持不变。

在实践中，O(log n) 和 O(1) 之间的差异是如此之小，以至于 C++ 的 STL 中的默认映射实现是基于 O(log n) 的(树而不是哈希)。