我遇到了这样一个问题：用push(x)、pop()和pop_max()方法实现一个队列。
pop_max()函数应该弹出遵循FIFO规则的最大元素。
例如：pop_max()之前：front->2,3,4,5,1,5
pop_max()之后：前->2,3,4,1,5
以下是我的一些尝试。
-
用基本队列实现它，使用支持队列用O(n)扫描找到最大元素。
pop()/push()是O(1)，pop_max()应该是O(n)。
-
使用双链表和单调堆栈实现它。
pop()/pop_max()是O(1)，push()应该是O(n)。
有人知道用最小的时间复杂度做这件事的方法吗？我读过这篇文章。实现一个队列，其中push_rear()、pop_front()和get_min()都是恒定时间操作，它提供的方法似乎不适合这种场景。
根据请求，这里有一个关于我为什么相信有一个最坏情况O(1)推和弹出和O(logn)的解决方案pop maxes这太复杂了，你不需要理解它用于面试。真的我写这个答案主要是为了娱乐[算法]标签正则化。
变量
n是结构中当前元素的数量，p是结构使用寿命内的推动次数。显然n≤p，且一般来说，log p不是O(log n)。
锦标赛树
主要的构建块是锦标赛树。锦标赛树是全二叉树(每个节点有零个或两个子节点)节点，使得具有标记为x和y的两个子节点的每个节点都被标记max(x，y)。从语义上讲，此数据结构的内容是具有零个子节点(叶子)的节点标签。如果你感到困惑，看看单淘汰赛的完整等级。
锦标赛树的有用之处在于我们可以订购树叶任何我们想要的方式。对于这个问题，我们需要队列顺序。根元素给出了总体最大值标签。找到最左边的叶子标签，如果标签与当前节点，否则为右侧节点。若要软删除叶，请设置其值为-∞，并将其祖先从父更新为根。
摊销的O(1)推送和最坏情况下的O(log p)弹出最大值
在实践中有更好的方法来实现这一点，但我们的目标是就是展示思想。
我们保存了一个O(log p)锦标赛树的链接列表。连接，它们叶子表示队列。每棵树都是一个完整的二叉树2k叶(计数中包括软删除元素)对于某个整数k≥0。
推送操作类似于在二进制数字上加一代表。我们将新元素单独放入锦标赛树中并将该树附加到列表中。而列表中的最后两棵树大小相同，通过制作第二个最后一个是一棵新树的左子树和右子树。
pop-max操作扫描树根以找到总体最大值，然后soft删除最左边的出现。
最坏情况O(1)推动
我们可以更懒地合并树木。而不是完成合并循环，我们保留一个延续队列。每次延续可以表示为指向列表中树的可变指针。到步骤它，我们将树的大小与其左邻居的大小进行比较；如果它们是相同的，然后合并树并更新指向合并的树。否则，继续操作完成。
push操作附加一个singleton树，附加一个continuation指向队列后面的树，然后继续在前面走几步。在任何给定的时间O(log p)合并需要继续，所以pop max仍然运行得足够快。(这来自摊余分析。)
常规pops
我们可以通过以下方式在最坏情况时间O(log p)中实现pop操作将双链表结构添加到锦标赛树中不会尚未删除。锦标赛使用软删除；此列表使用硬删除。
显然，我们希望pops在恒定的时间内运行。我们可以得到常数通过拆分最左边的锦标赛树来摊销时间，直到它软删除前的一个元素(需要某种屏障来确保之前的合并延续不使用此前缀)。
在最坏的情况下，恒定时间应该是可能的，有更多的调度，比如我们做了推。
最坏情况O(log n)pop最大值
别介意挥手，在这一点上，基本上是我的整个手臂。我们的策略是通过周期性地将p的有效值限制为O(n)在后台重建整个结构。这意味着发布pop重建的操作，并记住我们在重建中走了多远这样，如果需要的话，我们可以发布pop-maxe。假设我们做了多个推进每一次手术的重建，我们会在弹出和pop-maxes可以将元素计数减少一个以上的常量小部分
开放式问题
我相信有一种更清洁的方式来完成这一切。它是什么？
首先让我们讨论一个目标运行时间。我们可以使用这种抽象数据类型对n元素列表进行排序，其中n个push后面跟着n个pop-maxes。假设一般可比较元素，由于最快的可能比较排序是Θ(n-logn)，最坏情况下的推/弹出最大对必须是Ω(logn)。
在下面的C++中实现了获得所有三个操作的O(logn)最坏情况的一种方法。使用摊销会计，我们可以使推送O(logn)和弹出和弹出最大值免费。
这确实留下了一个问题，即我们是否可以获得最坏情况下的O(1)推送、O(1个)弹出和O(log n)弹出最大值。我相信答案是肯定的，但我心目中的解决方案相当复杂，涉及到对大小呈几何级数减少的队列段上的O(logn)锦标赛树的定期维护。
#include <list>
#include <map>
template <typename T> class QueueWithPopMax {
public:
void Push(T element) {
typename std::list<ListElement>::iterator back =
list_.insert(list_.end(), ListElement{});
back->iterator = multimap_.insert({element, back});
}
T Pop() {
T element = list_.front().iterator->first;
multimap_.erase(list_.front().iterator);
list_.pop_front();
return element;
}
T PopMax() {
T element = multimap_.begin()->first;
list_.erase(multimap_.begin()->second);
multimap_.erase(multimap_.begin());
return element;
}
private:
struct ListElement {
typename std::multimap<T, typename std::list<ListElement>::iterator,
std::greater<T>>::iterator iterator;
};
std::multimap<T, typename std::list<ListElement>::iterator, std::greater<T>>
multimap_;
std::list<ListElement> list_;
};
#include <iostream>
int main() {
QueueWithPopMax<int> queue;
queue.Push(2);
queue.Push(3);
queue.Push(4);
queue.Push(5);
queue.Push(1);
queue.Push(5);
std::cout << queue.PopMax() << "n";
std::cout << queue.Pop() << "n";
std::cout << queue.Pop() << "n";
std::cout << queue.Pop() << "n";
std::cout << queue.Pop() << "n";
std::cout << queue.Pop() << "n";
}