什么是适用于队列的正确数据结构，支持O(1)时间的最小值和最大值操作？

Question

什么是支持Enque、Dequeue、Peak、Min和Max操作并且所有这些操作的时间复杂度均为O(1)的队列的正确数据结构。

最显然的数据结构是链表，但是Min、Max操作将会是O(n)。优先队列是另一个完美的选择，但是Enqueue、Dequeue应该按照队列（FIFO）的正常方式工作。

另外一个我想到的选择是堆，但我无法想象如何使用堆来设计具有Min、Max操作的队列。

非常感谢任何帮助。

- bman

---

另外，程序员可能是一个更好的提问场所。 - Basile Starynkevitch

不，如果你弹出最小值或最大值，你的栈就不是O(1)了。 - Basile Starynkevitch

我假设“peak”是“peek”（并显示下一个将被出队的元素）。 - tucuxi

问题并不十分清晰：min()和max()是否会从结构中删除元素，还是只读的？如果是只读的话，那么O(1)的带有最小值和最大值的栈肯定是可行的（但不适用于队列）。如果不是只读的话，那么@BasileStarynkevitch是正确的，这样的结构将无法按预期工作。 - tucuxi

阅读了https://dev59.com/pW445IYBdhLWcg3wkLBG之后，使用只读的min和max似乎可以实现O(1)。我已经编辑了我的答案。 - tucuxi

Answer 1

您所需的数据结构如果min()和max()实际上改变了结构，则无法设计。如果min()和max()类似于peek()，并提供只读访问，则应按照此问题中的步骤进行操作，添加另一个deque，用于max()操作，类似于用于min()操作的deque。本答案的其余部分假定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的末尾，并通过其键将相同的节点添加到tree中的节点的HashMap。时间复杂度为O(log n)。
• 在 dequeue() 中，您需要从list的开头以及从其在树中的节点中的HashMap中删除该节点。时间复杂度为O(log n)。
• 在 min() 中，您需要查找树中的第一个元素。时间复杂度为O(1)。如果您需要删除它，则可以使用指向链表的指针，在这方面的时间复杂度为O(1);但是，如果它是具有特定K的最后一个元素，则重新平衡树的时间复杂度为O(log n)。
• 在 max() 中，相同的逻辑适用;除了您将寻找树中的最后一个元素。所以时间复杂度为O(log n)。
• 在 peek() 中，查看但不提取队列中的第一个元素的时间复杂度为O(1)。

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

实际上，在O(log n)和O(1)之间的差异非常小，以至于C++ STL中的默认映射实现是基于O(log n)的（使用Tree而不是Hash）。

- tucuxi

Answer 2

任何能够在O(1)时间内检索最小值或最大值的数据结构都需要每次插入和删除元素时至少花费O(log n)的时间以保持部分排序顺序。实现这一点的数据结构称为优先队列，而基本的优先队列支持Insert、Max和RemoveMax操作，建立它们的方法有很多种，但二叉堆是最好的。

支持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.

这种方法快速且占用内存较少，但需要非常小心地实现。

- Will Angley

Answer 3

这种结构是不存在的！

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

我们都知道，排序问题的复杂度是O(nlogn)。 但是，如果你所说的结构存在，就会有一种解决方案：

1. 逐个入队每个元素的成本为O(n)
2. 逐个出队最大（或最小）的元素的成本为O(n)

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

- lessmoon

---

不错的证明——任何实现修改 min() 或 max() 的结构都将意味着排序方面的重大突破。另一方面，不清楚 OP 是否指的是“只读”min()和max()。 - tucuxi

证明的开端不错，但还没有完全展开。你的假设似乎是我们没有排序好的列表。双向链表可以单独证明#2是错误的。这也似乎假定该结构不能有关于其在队列中位置的元信息。我承认用算法证明否定是极其困难的。也许再多迭代几次，就能证明了。但这远非不可能。 - Jdahern

我认为这是“这样的结构将是排序中的重大突破的证明”，而不是“这样的结构不可能存在的证明”。在第一种意义上，它是铁板钉钉的：如果你可以在O(n)内插入并在O(n)内删除最小值，那么你就可以在O(n)内排序（！！）。在第二个意义上，证明在少于O(n log n)的时间内进行排序是比@lessmoon的观察更难的。然而，许多非常聪明的人已经试图改进O(n log n)，而且可以肯定的是它不能被改进。对于基于二进制比较交换的算法也是如此证明的。 - tucuxi

嗯，最后一行“这意味着排序问题可以通过O(n)解决。但这是不可能的。”似乎证明了这样的结构是不可能存在的。我猜这是一种解释。祝你将来在证明中好运。 - Jdahern

Answer 4

假设：

您只关心性能，而不关心空间/内存等。

解决方案：

索引是一个集合，而不是列表（对于列表也可以工作，但可能需要一些额外的处理）

您可以同时使用队列和哈希表。

示例：

假设顺序是5 4 7 1 8 3

队列 -> 547813

哈希表 -> 134578

入队：

1）将对象插入正确的哈希表桶中，Min / Max始终是第一个和最后一个索引。（请参见排序的哈希表）

2）接下来，像正常情况下一样将其插入队列。

3）您可以/应该将两者链接起来。一个想法是使用哈希表值作为指向队列的指针。

使用大型哈希表的两个操作都将是O（1）

出队：

1）弹出第一个元素O（1）

2）从哈希表中删除元素O（1）

最小值/最大值：

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

有关排序哈希表的更好解释，请参见 https://dev59.com/XkvSa4cB1Zd3GeqPcCQB。

注意： 我想指出，我不知道有什么“正常”的数据结构能够满足您的要求。但这并不意味着不可能。如果您要尝试实现这个数据结构，很可能您将不得不根据自己的需求进行实现，并且无法使用当前可用的库。您可能需要考虑使用低级语言（如汇编语言）才能实现此目的，但如果您对 C 或 Java 熟悉，也许也能做到。

祝你好运

编辑： 我没有解释排序哈希表，因此添加了另一个 SO 的链接来解释它们。

- Jdahern

---

取决于您使用的哈希表。如果您使用的是一对一哈希表，其中插入在值上，则不需要。例如，如果我的数字范围是1到10，而我的映射是1到10，我可以让值在表中的行上进行插入。由于大多数数组插入不是O（1），所以我没有那样做。您的假设是哈希键与值无关，这很正常，但并不总是正确的。在插入值10时，将其插入到第10行，在值2上插入到第2行。我会编辑答案以更好地解释这部分内容。 - Jdahern

抱歉Jdhaern，但是链接的问题并没有解释“排序哈希表”-它只是请求它们。这样的数据结构不存在。它所接受的答案指向了一个TreeMap（没有以任何方式进行哈希，并且对于所有操作都是O(log n)）。你的答案仍然将HashMap的低成本与TreeMap的有序性质混合在一起；这仍然是一个错误的答案。 - tucuxi

你读了这些答案吗？我可能没有“解释”它们，但是给你提供了一些帮助。这很棘手，因为它涉及许多指针。我知道你来自Java背景，但需要考虑更低层次的东西。此外，这不是一个“普通”的哈希映射。你需要使用其他数据结构来帮助解决问题。你也应该看看TreeMaps，因为它们与我所描述的完全不同。你有100行，并且根据对象的值插入到行中。那不是TreeMap。 - Jdahern

论文：http://comjnl.oxfordjournals.org/content/17/2/135.full.pdf 还要看一下LinkedHashMaps。另一个文档是http://www.briandupreez.net/2011/03/simple-big-o-notation-post.html LinkedHashSet的get、add、remove和contains的时间复杂度为O(1)。 - Jdahern

好吧，我放弃了。你声称拥有20年以上的编程经验，却拼不对我的名字，而且你接受了不符合证明标准的证据，并告诉我一个数据集与我描述的不同。从现在开始，我们任何一方的争论都是毫无意义的。祝你好运。 - Jdahern