[Tutorial] Minimum Deque

Правка en2, от k1r1t0, 2023-11-04 02:14:05

Here I will describe a way to maintain deque that will allow us to find the smallest element in deque at any time. Maybe this technique is well-known, but I couldn’t find any info about it, so decided to post it there.

Minimum Stack and Minimum Queue

First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $$$O(1)$$$.

Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $$$O(N)$$$ amortized.

Minimum Deque

Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the number of moved elements: in the worst case we will move all elements every operation by removing first and last element alternately. So instead of moving all elements let's move only a half of them at a time. Turns out it works in $$$O(N)$$$!

But how to prove it? Let $$$k_i$$$ be the number of elements deque contained right before $$$i_{th}$$$ operation, the algorithm above obviously works in $$$O(N + \sum k_i)$$$. Also $$$k_i = \frac{k_{i-1}}{2} + q_i$$$, where $$$q_i$$$ is the number of elements added between operations $$$i-1$$$ and $$$i$$$. We can see that $$$q_i$$$ contributes $$$q_i$$$ to $$$k_i$$$, $$$\frac{q_i}{2}$$$ to $$$k_{i+1}$$$, $$$\frac{q_i}{4}$$$ to $$$k_{i+2}$$$ and so on. It follows that $$$q_i$$$ contributes $$$O(q_i)$$$ to $$$O(\sum k_i)$$$. $$$\sum q_i$$$ is obviously $$$\leq N$$$, so $$$O(\sum k_i) = O(N)$$$. That's why the algorithm above is $$$O(N)$$$ amortized.

Implementation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский k1r1t0 2023-11-04 02:14:05 2 (published)
en1 Английский k1r1t0 2023-11-04 02:13:19 3176 Initial revision (saved to drafts)