algorithm - 使用 push(x)、pop() 和 pop_max() 方法实现队列
问题描述
我遇到了这样一个问题：使用 push(x)、pop() 和pop_max()方法实现一个队列。
pop_max() 函数应该按照 FIFO 规则弹出最大的元素。
eg：在pop_max()之前：front-> 2,3,4,5,1,5
pop_max() 之后：front-> 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(log n) 最大弹出的解决方案。它非常复杂，你不需要在面试中理解它。真的。我写这个答案主要是为了娱乐 [算法] 标签常客。
变量
n 是当前结构中的元素数量，p 是结构生命周期中的推送次数。显然 n ≤ p，一般来说，log p 不是 O(log n)。
比赛树
主要构建块是锦标赛树。锦标赛树是具有标记节点的完整二叉树（每个节点有零个或两个子节点），因此每个具有两个标记为 x 和 y 的子节点的节点都标记为 max(x, y)。从语义上讲，该数据结构的内容是具有零个子节点（叶子）的节点的标签。如果您感到困惑，请查看单淘汰锦标赛的完整括号。
锦标赛树的有用之处在于我们可以以任何我们想要的方式对叶子进行排序。对于这个问题，我们需要队列顺序。根元素给出了整体最大标签。要找到具有该标签的最左边的叶子，如果它的标签与当前节点相同，则重复下降到左子节点，否则下降到右节点。要软删除叶子，请将其值设置为 -∞ 并将其祖先从父节点更新为根节点。
摊销 O(1) 推送和最坏情况 O(log p) 弹出最大值
在实践中有更好的方法来实现这一点，但我们的目标是展示想法。
我们保留一个 O(log p) 锦标赛树的链表。串联起来，它们的叶子代表队列。对于某个整数 k ≥ 0，每棵树都是具有 2 k个叶子的完整二叉树（软删除的元素包含在计数中）。
推送操作类似于将二进制表示的数字加一。我们将新元素单独放入锦标赛树中，并将该树附加到列表中。虽然列表中的最后两棵树具有相同的大小，但通过使倒数第二个成为新树的左子节点和最后一个右子节点，将它们组合成一棵树。
pop-max 操作扫描树根以找到整体最大值，然后软删除最左边的出现。
最坏情况 O(1) 推送
我们可以更懒惰地合并树木。我们保留一个延续队列，而不是立即完成合并循环。每个延续都可以表示为指向列表中树的可变指针。为了步进它，我们将树的大小与其左邻居的大小进行比较；如果它们相同，则合并树并更新指向合并树的指针。否则，继续完成。
推操作附加一个单例树，将一个指向该树的延续附加到队列的后面，然后在前面继续工作几个步骤。在任何给定时间，都会有 O(log p) 次合并继续进行，因此 pop-max 仍然运行得足够快。（这来自摊销分析。）
定期流行音乐
我们可以在最坏情况时间 O(log p) 中实现弹出操作，方法是向锦标赛树中的尚未删除的叶子添加一个双向链表结构。比赛使用软删除；此列表使用硬删除。
显然，我们希望 pop 在恒定时间内运行。我们可以通过在软删除之前拆分最左边的锦标赛树直到它有一个元素来获得恒定 的摊销时间（使用某种障碍来确保之前的合并延续不理会这个前缀）。
最坏情况下的恒定时间应该可以通过更多的调度来实现，就像我们为推送所做的那样。
最坏情况 O(log n) pop-maxes
没关系挥手，此时它基本上是我的整个手臂。我们的策略是通过定期在后台重建整个结构来将 p 的有效值限制为 O(n)。这意味着向重建发出 pop 操作并记住我们在重建中的距离，以便我们可以在需要时发出 pop-maxes。假设我们在每个操作中对重建进行多次推送，我们将在 pop 和 pop-maxes 将元素计数减少超过一个常数之前完成。
开放式问题
我确信有一种更清洁的方法可以完成这一切。它是什么？