0

I am just wondering, whether it's possible to implement a structure (list/deque) which would have O(1) complexity (const/amortized doesn't matter) for get_min(), push_back(), push_front(), pop_back(), pop_front() operations?

It's definitely possible to implement stack or even queue (for them push() and pop() are available only for one end) which will satisfy these conditions. But I wasn't able to reuse this logic to a dequeue case.

It's also possible to create structure which will have O(logn) complexity for pushes/pops and O(1) for get_min (just using simple list and min_heap in which deletion of arbitrary element for O(logn) is available).

But still amortized O(1) for all operations seems impossible for me. If that is the case, can the information about exact number of operations (or max possible number of elements in list) n helps (simpler case)? Can we somehow use O(n) (or even more) additional memory or smth like this?

bifrosu
  • 13
  • 3

1 Answers1

3

It is indeed possible to build a min-deque where the push-front, push-back, and find-min operations work in worst-case time O(1) and the pop-front and pop-back operations take amortized time O(1). The easiest route that I know goes like this:

  1. First, make a stack that supports push, pop, and find-min in time O(1). We’ll use this as a building block.
  2. Use the construction that builds a deque out of three stacks, except using these min-stacks instead of regular stacks. You can then implement the find-min operation by querying each of the three stacks for its minimum element and returning the min of those values.

In case you haven’t seen how to do step (2), the idea is a generalization of how to make a queue from two stacks. You maintain two stacks representing the elements of the deque such that one stack represents the front of the deque in reverse order (stack top is the front of the deque, and deeper elements are the next elements of the deque) and the elements of the other stack represent the back of the deque (top element is the last element of the deque, deeper elements go backwards through the deque). For example, here’s one way to encode the deque 1, 2, 3, ..., 10:

front: | 7 6 5 4 3 2 1
back:  | 8 9 10

To push onto the front or back of the deque, just do a push onto the appropriate deque. To pop the front or back of the deque, if the appropriate stack is nonempty, just pop from it. Otherwise, if the stack is empty, you need to move some number of elements from the other stack over. Specifically, to keep things balanced between the two stacks, you do a series of pushes and pops to put half the elements into each of the two stacks. That looks like this:

  1. Pop half the elements from the other stack and push them onto a temporary stack.
  2. Pop the remaining elements from the other stack and push them onto the empty stack.
  3. Pop the elements from the temporary stack and push them back onto the other stack.

You can show using a potential argument (see Φ to be the absolute value of the difference in heights of the two stacks) that each operation takes amortized time O(1).

It may be possible to somehow speed this up to worst-case O(1) time per operation using some sort of scheduling scheme, but I’m not sure how to do this. I know there’s a way to implement a queue with four stacks with worst-case O(1) for each operation, so perhaps this idea could be generalized to work here?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    @ALX23x Your edit doesn’t use standard terminology, and OP already specified that amortised complexity works for them, so the edit is also redundant. – Konrad Rudolph Sep 06 '20 at 16:37
  • Think that you are right: this is the actual way how to reapply this [queue](https://stackoverflow.com/questions/4802038/implement-a-queue-in-which-push-rear-pop-front-and-get-min-are-all-consta) logic to deque (that i wasn't able to figured out myself). Just need a couple of minutes to think about it more carefully (to prevent false accept), and then going to mark your answer as right. Thank you! – bifrosu Sep 06 '20 at 16:40
  • @KonradRudolf it is important to specify in answer what kind of O(1) it is. The stack implementation is O(1) maximum. Also I was not familiar with the "amortised" which caused it to be ignored. The "at maximum" and "on average" are fairly common and easy to understand. – ALX23z Sep 06 '20 at 16:54
  • @ALX23z There is an important distinction between “on average” and “amortized” that makes the terms not interchangeable. “On average” is ambiguous as to what is being averaged over and could imply randomness. “Amortized” means “any sequence of these operations is guaranteed to take no more than this amount of time, divided across the number of operations performed.” See [these lecture slides](http://web.stanford.edu/class/archive/cs/cs166/cs166.1206/lectures/07/Slides07.pdf) for more on amortization. – templatetypedef Sep 06 '20 at 17:07
  • 1
    @templatetypedef I'm pretty sure you can decorate the real-time functional deque due to [Kaplan and Tarjan](http://www.math.tau.ac.il/~haimk/adv-ds-2000/jacm-final.pdf) with subtree minimums, though perhaps there's some subtle detail that I missed. – David Eisenstat Sep 06 '20 at 22:23