algorithm - 在 O(1) 中设计一个堆栈 + findmin 和 deletemin？

Question

我在 O(1) 时间内看到了有关使用 findmin 设计堆栈的问题的答案：

如果请求相同怎么办：

Devise a stack-like data structure that does push, pop and min (or max) operations 
in O(1) time. There are no space constraints.

但是 deletemin 也应该在 O(1) 中？可能吗？

score 5 · Accepted Answer

不，它不能完成 - 因为它会允许O(n)排序。

Assume there is such a DS, let it be D
Let A be an input array.
push all elements from A to D.
while D is not empty:
   yield D.min()
   D.popMin()

以上将在O(n)假设popMin()and min()are的情况下运行O(1)，并将对数组进行排序。
但是，排序是 Omega(nlogn) 问题。矛盾。
因此我们可以得出结论，这样的 DS 不存在，

1 回答 1