[4,2,5,1]（顶部为1）变为[(4,4), (2,2), (5,2), (1,1)]。pop请求，将第一个栈中的所有元素[(4,4), (2,2), (5,2), (1,1)]移动，第二个栈将是[(1,1), (5,1), (2,1), (4,1)]。现在从第二个栈返回顶部元素。get_min()和push()以及平摊O(1)的pop()。好的 - 我认为我有一个答案，可以让你执行这些操作的时间复杂度均摊为 O(1)，意味着任何一个操作都可能需要 O(n) 的时间，但是 n 个操作的序列只需每个操作 O(1) 时间。
这个想法是将数据存储为 笛卡尔树。 这是一棵遵循最小堆属性（每个节点都不大于其子节点）并以一种使得其中序遍历返回添加顺序相同的节点的方式排序的二叉树。例如，下面是一个由序列 2 1 4 3 5 构成的笛卡尔树：
1
/ \
2 3
/ \
4 5
可以通过以下方法在O(1)摊销时间内将元素插入笛卡尔树中。查看树的右侧脊柱（由始终向右走形成的从根到最右叶子的路径）。从最右边的节点开始，沿着这条路径向上扫描，直到找到第一个小于要插入的节点的节点。
更改该节点，使其右子节点为这个新节点，然后将该节点的旧右子节点作为刚刚添加的节点的左子节点。例如，假设我们想将另一个2的副本插入以上树中。我们沿着右侧脊柱向上走过5和3，但在1下停止，因为1 < 2。然后我们改变树的样子如下:
1
/ \
2 2
/
3
/ \
4 5
注意中序遍历给出的顺序是 2 1 4 3 5 2，这是我们添加值的顺序。
这个算法的平摊复杂度为 O(1)，因为我们可以创建一个势能函数，等于树右脊中节点的数量。插入一个节点所需的真实时间是 1 加上我们考虑的脊长为 k 的节点数（称之为 k）。一旦找到插入节点的位置，脊的大小缩小了 k - 1，因为我们访问的 k 个节点不再在右脊上，而新节点就在它们的位置上。这给出了平摊成本为 1 + k + (1 - k) = 2 = O(1)，即每次插入的平摊复杂度为 O(1)。另一种思考方式是，一旦将一个节点移出右脊，它永远不会再成为右脊的一部分，因此我们永远不需要再次移动它。由于每个节点最多只能被移动一次，这意味着 n 次插入最多可以进行 n 次移动，因此总运行时间最多为 O(n)，对于每个元素的平摊复杂度为 O(1)。
要执行弹出操作，我们只需从笛卡尔树中删除最左节点。如果这个节点是叶子节点，则我们已经完成。否则，该节点只能有一个孩子（右孩子），因此我们用其右孩子替换它。只要跟踪最左边的节点在哪里，这一步就需要 O(1) 的时间。但是，在删除最左节点并用其右孩子替换它后，我们可能不知道新的最左节点在哪里。为了解决这个问题，我们只需从刚刚移动到最左孩子的新节点开始沿树的左脊向下走。我声称这仍然在 O(1) 平摊时间内运行。要证明这一点，请注意在找到最左节点的任何一次遍历中，每个节点最多被访问一次。要了解这一点，请注意，一旦以这种方式访问了一个节点，唯一需要再次查看它的方法是将其从最左节点的孩子移动到最左节点。但是，所有被访问的节点都是最左节点的父节点，因此这种情况不会发生。因此，在此过程中每个节点最多被访问一次，弹出操作的复杂度为 O(1)。
我们可以在 O(1) 时间内找到最小值，因为笛卡尔树可以免费让我们访问树中最小的元素；它是树的根节点。
最后，要查看节点是否按插入顺序返回，请注意笛卡尔树始终将其元素存储在中序遍历访问它们的排序顺序中。由于我们总是在每一步中删除最左节点，而这是中序遍历的第一个元素，因此我们总是按照它们被插入的顺序获取节点。
简而言之，我们得到了 O(1) 平摊推和弹出，以及 O(1) 最坏情况下的查找最小值。
如果我能想出最坏情况下 O(1) 的实现，我一定会发布它。这是一个很好的问题；感谢您的发布！
好的，以下是一种解决方案。
首先，我们需要一些可以提供 push_back()、push_front()、pop_back() 和 pop_front() 的东西，时间复杂度为 O(1)。使用数组和 2 个迭代器实现很容易。第一个迭代器将指向前面，第二个将指向后面。让我们称这样的东西为 deque。
这是伪代码：
class MyQueue//Our data structure
{
deque D;//We need 2 deque objects
deque Min;
push(element)//pushing element to MyQueue
{
D.push_back(element);
while(Min.is_not_empty() and Min.back()>element)
Min.pop_back();
Min.push_back(element);
}
pop()//poping MyQueue
{
if(Min.front()==D.front() )
Min.pop_front();
D.pop_front();
}
min()
{
return Min.front();
}
}
解释：
例如，让我们将数字 [12,5,10,7,11,19] 推入到我们的 MyQueue 中。
1) 推入 12
D [12]
Min[12]
2)向数组中添加元素5
D[12,5]
Min[5] //5>12 so 12 removed
3)将10推入
D[12,5,10]
Min[5,10]
4)推入7
D[12,5,10,7]
Min[5,7]
6)将11推入
D[12,5,10,7,11]
Min[5,7,11]
7) 将19推入数组
D[12,5,10,7,11,19]
Min[5,7,11,19]
现在让我们调用pop_front()
我们得到的结果是
D[5,10,7,11,19]
Min[5,7,11,19]
最小值为5
让我们再次调用pop_front()
解释：pop_front将从D中移除5，但它也会弹出Min的前面元素，因为它等于D的前面元素（5）。
D[10,7,11,19]
Min[7,11,19]
最小值为7. :)
from collections import deque
class MinQueue(deque):
def __init__(self):
deque.__init__(self)
self.minq = deque()
def push_rear(self, x):
self.append(x)
while len(self.minq) > 0 and self.minq[-1] > x:
self.minq.pop()
self.minq.append(x)
def pop_front(self):
x = self.popleft()
if self.minq[0] == x:
self.minq.popleft()
return(x)
def get_min(self):
return(self.minq[0])
class LinkedListElement
{
LinkedListElement next;
int currentMin;
}
你可以有两个指针，一个指向开始，另一个指向结束。
如果你要将元素添加到队列的开头，请检查开始指针和要插入的节点。如果要插入的节点currentmin小于start currentmin，那么node to insert currentmin是最小值。否则，用 start currentmin 更新当前最小值。
对enque执行相同操作。
JavaScript 实现
(感谢 adamax's solution 的灵感；我基于其实现了一个类似的实现。向下滚动到底部查看完全注释的代码或者阅读下面的一般步骤。请注意，这个方法在O(1)常数时间内找到最大值而不是最小值--很容易改变):
总体思路是在构建
MaxQueue时创建两个栈（我使用链表作为底层Stack数据结构--未包含在代码中；但只要实现了O(1)插入/删除的任何Stack都可以）。一个我们将主要从中pop（dqStack），另一个我们将主要push到（eqStack）。
enqueue操作，如果MaxQueue为空，我们将会在元组中存储当前最大值和该值，并将其与值一同压入dqStack中（由于它是MaxQueue中唯一的值，因此这两个值相同）;例如：const m = new MaxQueue();
m.enqueue(6);
/*
the dqStack now looks like:
[6, 6] - [value, max]
*/
MaxQueue不为空，我们只将value推入eqStack；m.enqueue(7);
m.enqueue(8);
/*
dqStack: eqStack: 8
[6, 6] 7 - just the value
*/
/*
dqStack: eqStack: 8
[6, 8] 7
*/
对于
dequeue操作，我们将从dqStack中pop并返回元组中的值。
m.dequeue();
> 6
// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/
dqStack 为空，将 eqStack 中的所有值移动到 dqStack 中，例如：// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);
/*
the stacks will look like:
dqStack: eqStack: 1
4
2
[3, 5] 5
*/
maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3
// as dequeue moves one value over, it checks if it's greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update eqStack:
[2, 4] => 2 < 4 - no update
[4, 4] => 4 > 1 - update
[1, 1] => 1st value moved over so max is itself empty
*/
dqStack一次，我们可以说dequeue的平摊时间复杂度为O(1)。getMax以在O(1)的常数时间内检索当前最大值。只要MaxQueue不为空，最大值就可以轻松地从dqStack中的下一个元组中取出。maxQ.getMax();
> 5
// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/
class MaxQueue {
constructor(...data) {
// create a dequeue Stack from which we'll pop
this.dqStack = new Stack();
// create an enqueue Stack to which we'll push
this.eqStack = new Stack();
// if enqueueing data at construction, iterate through data and enqueue each
if (data.length) for (const datum of data) this.enqueue(datum);
}
enqueue(data) { // O(1) constant insertion time
// if the MaxQueue is empty,
if (!this.peek()) {
// push data to the dequeue Stack and indicate it's the max;
this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
} else {
// otherwise, the MaxQueue is not empty; push data to enqueue Stack
this.eqStack.push(data);
// save a reference to the tuple that's next in line to be dequeued
const next = this.dqStack.peek();
// if the enqueueing data is > the max in that tuple, update it
if (data > next[1]) next[1] = data;
}
}
moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
// start max at -Infinity for comparison with the first value
let max = -Infinity;
// until enqueue Stack is empty,
while (this.eqStack.peek()) {
// pop from enqueue Stack and save its data
const data = this.eqStack.pop();
// if data is > max, set max to data
if (data > max) max = data;
// push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
this.dqStack.push([data, max]);
}
}
dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// pop from the dequeue Stack and save it's data
const [data] = this.dqStack.pop();
// if there's no data left in dequeue Stack, move all data from enqueue Stack
if (!this.dqStack.peek()) this.moveAllFromEqToDq();
// return the data
return data;
}
peek() { // O(1) constant peek time
// if the MaxQueue is empty, return undefined
if (!this.dqStack.peek()) return;
// peek at dequeue Stack and return its data
return this.dqStack.peek()[0];
}
getMax() { // O(1) constant time to find maximum value
// if the MaxQueue is empty, return undefined
if (!this.peek()) return;
// peek at dequeue Stack and return the current max
return this.dqStack.peek()[1];
}
}如果您不介意存储一些额外的数据，那么存储最小值应该是非常简单的。如果新添加或删除的元素是最小值，push和pop可以更新该值，获取最小值只需获取变量的值即可。
这是假设get_min()不改变数据的情况下；如果您更喜欢像pop_min()这样的东西（即删除最小元素），您可以简单地存储指向实际元素及其前一个元素（如果有）的指针，并使用push_rear()和pop_front()相应地更新它们。
在评论后进行编辑：
显然，在这些操作中，如果最小值发生变化，则会导致O(n)的push和pop，因此严格来说不符合要求。
我们知道push和pop是常数时间操作[精确地说是O(1)]。
但是当我们想到get_min()[即查找队列中当前最小的数字]时，通常首先想到的是每次请求最小元素时搜索整个队列。但这永远不会给出常数时间操作，这是问题的主要目标。
这通常在面试中经常被问到，所以你必须知道诀窍。
为了做到这一点，我们必须使用另外两个队列来跟踪最小元素，并且我们必须在队列上执行push和pop操作时修改这两个队列，以便在O(1)时间内获得最小元素。
以下是基于上述方法的自描述伪代码。
Queue q, minq1, minq2;
isMinq1Current=true;
void push(int a)
{
q.push(a);
if(isMinq1Current)
{
if(minq1.empty) minq1.push(a);
else
{
while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
minq2.push(a);
while(!minq1.empty) minq1.pop();
isMinq1Current=false;
}
}
else
{
//mirror if(isMinq1Current) branch.
}
}
int pop()
{
int a = q.pop();
if(isMinq1Current)
{
if(a==minq1.top) minq1.pop();
}
else
{
//mirror if(isMinq1Current) branch.
}
return a;
}
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
queue<int> main_queue;
deque<int> min_queue;
void clearQueue(deque<int> &q)
{
while(q.empty() == false) q.pop_front();
}
void PushRear(int elem)
{
main_queue.push(elem);
if(min_queue.empty() == false && elem < min_queue.front())
{
clearQueue(min_queue);
}
while(min_queue.empty() == false && elem < min_queue.back())
{
min_queue.pop_back();
}
min_queue.push_back(elem);
}
void PopFront()
{
int elem = main_queue.front();
main_queue.pop();
if (elem == min_queue.front())
{
min_queue.pop_front();
}
}
int GetMin()
{
return min_queue.front();
}
int main()
{
PushRear(1);
PushRear(-1);
PushRear(2);
cout<<GetMin()<<endl;
PopFront();
PopFront();
cout<<GetMin()<<endl;
return 0;
}
这个解决方案包含2个队列：
1. main_q - 存储输入的数字。
2. min_q - 根据某些规则存储最小数字，这些规则将在函数MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min()中描述。
以下是Python代码。队列使用List实现。
主要思想在于MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min()函数中。
一个关键假设是清空队列需要o(0)时间。
测试在末尾提供。
import numbers
class EmptyQueueException(Exception):
pass
class BaseQ():
def __init__(self):
self.l = list()
def enqueue(self, x):
assert isinstance(x, numbers.Number)
self.l.append(x)
def dequeue(self):
return self.l.pop(0)
def peek_first(self):
return self.l[0]
def peek_last(self):
return self.l[len(self.l)-1]
def empty(self):
return self.l==None or len(self.l)==0
def clear(self):
self.l=[]
class MainQ(BaseQ):
def __init__(self, min_q):
super().__init__()
self.min_q = min_q
def enqueue(self, x):
super().enqueue(x)
if self.min_q.empty():
self.min_q.enqueue(x)
elif x > self.min_q.peek_last():
self.min_q.enqueue(x)
else: # x <= self.min_q.peek_last():
self.min_q.clear()
self.min_q.enqueue(x)
def dequeue(self):
if self.empty():
raise EmptyQueueException("Queue is empty")
x = super().dequeue()
if x == self.min_q.peek_first():
self.min_q.dequeue()
return x
def get_min(self):
if self.empty():
raise EmptyQueueException("Queue is empty, NO minimum")
return self.min_q.peek_first()
INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))
if __name__ == '__main__':
min_q = BaseQ()
main_q = MainQ(min_q)
try:
for operator, i in INPUT_NUMS:
if operator=="+":
main_q.enqueue(i)
print("Added {} ; Min is: {}".format(i,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
else:
x = main_q.dequeue()
print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
print("main_q = {}".format(main_q.l))
print("min_q = {}".format(main_q.min_q.l))
print("==========")
except Exception as e:
print("exception: {}".format(e))
"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum
Process finished with exit code 0