自定义数据结构，具有常数时间的push和popmin操作。

Question

3

我最近在面试中遇到了这个问题：

设计一个数据结构，支持以下两个操作： 1. push(N) - 存储一个数字 2. popmin() - 提取所有存储数字中的最小值，并从存储中删除它 push和popmin操作都必须在O(1)时间内执行。

起初我考虑使用两个栈，但这只能获取最小数，无法移除它。

有什么想法吗？

- ChrisU

6

似乎不可能，因为您可以使用这样的数据结构来实现线性时间排序。 - Vaughn Cato

2

存储的数字是否有其他限制（例如，整数在给定范围内）？我认为当前版本的问题是无法解决的，因为具有O(1)的push和pop_min的数据结构将允许构建一个O(n)的排序算法。众所周知，基于比较的排序的最佳情况是O(n*log(n))... - Darren Engwirda

你可以使用主队列，但是对于一个项目的插入没有常数时间。 - Roman Pekar

我认为你们都是正确的。这可能是个捉弄问题。无论如何，还是谢谢！ - ChrisU

2个回答

1

有很多堆可以在O(1)的时间内进行插入和查找最小值。问题是删除最小值需要O(log N)的时间。这似乎暗示着要么信息缺失，要么信息错误。

- Nuclearman

我认为你是对的。这可能是一个有技巧的问题。无论如何，谢谢！ - ChrisU

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

这里有一个快速证明，在比较模型中是不可能的。从n个值开始，依次将它们推入堆栈，然后执行n次popmin操作。这将以O(n)的时间返回按排序顺序排列的元素，违反了Ω(n log n)的排序限制。