c++ - 所有推送/弹出（前/后）和 get_min() 都是 O(1) 操作的双端队列

Question

我只是想知道，是否有可能实现一个结构（list/deque），它对操作具有复杂O(1)性（const/amortized 无关紧要）get_min(), push_back(), push_front(), pop_back(), pop_front()？

绝对有可能实现满足这些条件的堆栈甚至队列（对于它们push()并且pop()仅用于一端）。但我无法将此逻辑重用于出队案例。

也可以创建对推送/弹出和for具有O(logn)复杂性的结构（仅使用简单列表并且可以删除任意元素 ）。O(1)get_minmin_heapO(logn)

但对我来说，所有操作仍然摊销O(1)似乎是不可能的。如果是这种情况，关于操作的确切数量（或列表中可能的最大元素数量）的信息是否有n帮助（更简单的情况）？我们能以某种方式使用O(n)（甚至更多）额外的内存或像这样的东西吗？

标签： c++algorithmdata-structuresminpriority-queue

Answer 1

确实可以构建一个最小双端队列，其中前推、后推和查找最小操作在最坏情况时间 O(1) 中工作，而前弹出和后弹出操作需要摊销时间 O( 1）。我知道的最简单的路线是这样的：

1. 首先，在 O(1) 时间内创建一个支持 push、pop 和 find-min 的堆栈。我们将使用它作为构建块。
2. 使用从三个堆栈构建双端队列的结构，除了使用这些最小堆栈而不是常规堆栈。然后，您可以通过查询三个堆栈中的每一个堆栈的最小元素并返回这些值的最小值来实现 find-min 操作。

如果您还没有看到如何执行步骤 (2)，那么这个想法是对如何从两个堆栈创建队列的概括。您维护两个代表双端队列元素的堆栈，一个堆栈以相反的顺序代表双端队列的前端（堆栈顶部是双端队列的前端，更深的元素是双端队列的下一个元素）和另一个的元素stack 代表双端队列的后面（顶部元素是双端队列的最后一个元素，更深的元素通过双端队列向后）。例如，这是对双端队列 1、2、3、...、10 进行编码的一种方法：

front: | 7 6 5 4 3 2 1
back:  | 8 9 10

要推入双端队列的前面或后面，只需推入相应的双端队列即可。要弹出双端队列的前部或后部，如果适当的堆栈非空，只需从中弹出即可。否则，如果堆栈为空，则需要将一些元素从另一个堆栈移过来。具体来说，为了保持两个堆栈之间的平衡，您执行一系列推送和弹出操作以将一半元素放入两个堆栈中的每一个中。看起来像这样：

1. 从另一个堆栈中弹出一半元素并将它们推送到临时堆栈中。
2. 从另一个堆栈中弹出剩余的元素并将它们压入空堆栈。
3. 从临时堆栈中弹出元素并将它们推回另一个堆栈。

您可以使用潜在参数（请参阅 Φ 是两个堆栈高度差的绝对值）表明每个操作需要分摊时间 O(1)。

有可能使用某种调度方案以某种方式将每次操作的最坏情况 O(1) 时间加速到此，但我不确定如何做到这一点。我知道有一种方法可以实现一个有四个堆栈的队列，每个操作的最坏情况为 O(1)，所以也许这个想法可以推广到这里工作？