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

Question

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

最明显的数据结构是链表，但 Min、Max 运算的时间复杂度为 O(n)。优先队列是另一个完美的选择，但入队、出队应该以队列的正常方式工作。（先进先出）

想到的另一个选项是堆，但我不太明白如何使用堆设计具有最小、最大操作的队列。

非常感谢任何帮助。

Answer 1

如果min()和max()实际上改变了结构，则无法设计您寻求的数据结构。如果min()和max()类似于peek()，并且提供只读访问，那么你应该按照this question中的步骤，添加另一个类似于min()操作的双端队列以供使用在 max() 操作中。该答案的其余部分假设 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).
在 dequeue() 上，您将从 list 的开头删除节点，并从其树中节点的 HashMap 中删除该节点。 O(log n).
在 min() 上，您将查找树中的第一个元素。 O（1）。如果你需要删除它，你有指向链表的指针，所以 O(1) 在那边；但是 O(log n) 如果它是具有特定 K 的最后一个元素，则重新平衡树。
在max()上，同样的逻辑适用；除了你要寻找树中的最后一个元素。所以 O(log n).
在 peek() 上，查看但不提取队列中的第一个元素将是 O(1).

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

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

Answer 2

假设：

您只关心性能而不关心 space/内存/...

一个解决方案:

索引是一个集合，而不是列表（适用于列表，但可能需要一些额外的爱）

您可以并排执行队列和散列 table。

示例：

假设顺序是 5 4 7 1 8 3

队列 -> 547813

哈希 table -> 134578

排队：

1) 取出你的对象，并插入右桶中的散列 table Min / Max 将始终是第一个和最后一个索引。（参见排序哈希 tables）

2) 接下来，像往常一样插入您的队列。

3) 你可以/应该link 两者。一种想法是使用散列 table 值作为指向队列的指针。

具有大散列的两个操作 table 将是 O(1)

出队:

1) 弹出第一个元素O(1)

2) 从散列中删除元素 table O(1)

最小/最大：

1) 查看您的哈希 table。根据所使用的语言，理论上您可以通过查看 table 的头部或 table 的尾部来找到它。

为了更好地解释排序哈希 tables，

注意: 我想指出，据我所知，没有 "normal" 数据结构可以满足您的要求。但是，这并不意味着不可能。如果您打算尝试实现数据结构，很可能您将不得不根据您的需要来实现，并且将无法使用当前可用的库。为了实现这一点，您可能需要考虑使用非常低级的语言，如汇编，但如果您擅长这些语言，也许 C 或 Java 可以做到。

祝你好运

已编辑：我没有解释排序哈希 tables，所以在另一个 SO 中添加了一个 link 来解释它们。

Answer 3

这个结构不存在！

有一个简单的方法可以证明这个结论。

众所周知，排序问题的复杂度是O(nlogn)。但是如果你说的结构存在，那么排序会有解决方案：

逐一查询每个元素成本O(n)
将每个最大（或最小）元素逐一出列成本 O(n)

这意味着排序问题可以用O(n)来解决。但是不可能。

Answer 4

任何可以在 O(1) 时间内检索 Min 或 Max 的数据结构需要至少花费 O(log n) Insert 和 Remove 以部分排序的顺序维护元素。实现此目的的数据结构称为 优先级队列 。

基本优先级队列支持Insert、Max和RemoveMax。有多种构建它们的方法，但是 binary heaps work best.

使用单个优先级队列支持所有 Insert、Min、RemoveMin、Max 和 RemoveMax 更加复杂。论文中描述了一种使用从二叉堆改编而来的单一数据结构来做到这一点的方法：

Atkinson, Michael D., et al. "Min-max heaps and generalized priority queues." Communications of the ACM 29.10 (1986): 996-1000.

它速度快且内存效率高，但需要非常小心才能正确实施。

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

What is the right data structure for a queue that support Min, Max operations in O(1) time?

heap

queue