从队列中获取O(1)时间的最小值/最大值？

Question

如何在0(1)时间复杂度的任何时间从队列中检索max和min元素？之前我使用Collections.max和min来查找元素,但这将是0(n).

Answer 1

存在这样的结构,其作用类似于队列但允许您在恒定时间内检索最小/最大值,实际上不是严格恒定的,它是分摊的常量时间(可以猜测命名为最小/最大队列).有两种方法可以实现它 - 使用两个堆栈或使用队列和双端队列.

Deque实现看起来更像这样(语言不可知):

所以我们有一个最大元素的双端队列,前面的那个是所需的最大元素,以及一个标准的队列.

推动操作

1. 如果队列为空,只需按下队列和双端队列上的元素即可.
2. 如果队列不为空,则推送队列中的元素,从deque的后面开始删除严格小于我们正在推送的元素的所有元素(它们将不会是最大值,因为推送的元素更大并将在队列中持续更长时间)并将当前元素推送到双端队列的背面

删除操作

1. 如果双端队列的前面等于队列的前面,则弹出两个(从前面开始)
2. 如果双端队列的前端不等于队列的前面然后只弹出队列,那么poped元素肯定不是最大的一个.

获得最大值

1. 它只是双端队列的第一个元素.

(应该添加许多参数以明确其工作原理,但下面提供的第二个版本可能是这种必要性的答案)

Stack实现非常相似,我认为实现起来可能要长一些,但也许更容易掌握.首先要注意的是,很容易将最大元素存储在堆栈中 - 简单的练习(对于懒惰的 - 使用find-min/find-max的堆栈比O(n)更有效？).第二部分,如果第一次看到,可能有点棘手,是使用两个堆栈实现队列非常容易,可以在这里找到 - 如何使用两个堆栈实现队列？.基本上就是这样 - 如果我们可以获得两个堆栈的最大元素,我们就可以获得整个队列的最大元素(如果你想要一个更正式的参数,取最大值是关联的或类似的东西,但我打赌你不要不,这很明显.

最小版本以类似方式完成.

一切也可以在O(nlogn)时间内使用一组(或类似的东西)来完成,但它没有意义,因为O(n)中的常量非常小,它应该更快,但更容易实现.

第一版的非有趣部分:

希望我帮了一下.并希望没有说错.如果需要,可以在C++/C中提供简单的实现.将不胜感激任何关于表格的反馈,因为这是我在任何地方的第一篇文章:)(英语不是我的母语).还有一些关于正确性的确认会很棒.

编辑:因为这个答案给了我一些观点,我觉得有必要对它进行一点清理,并将其扩展一点.

Answer 2

您只有两种方法可以获得最小/最大操作的O(1):

• 如果结构已排序,您知道最大/最小位置
• 如果结构未排序且仅允许插入:您可以在每次插入项目时重新计算最小值/最大值并单独存储值
• 如果结构没有排序并允许插入和删除:我认为你不能做得比O(n)更好,除非你使用多个集合(但该解决方案不支持删除任何元素,只有头/尾元素,应该是队列的情况).