array empty cell search algorithm

Question

I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid.

Here is my scenario:

1. Consider an empty array named ARR with size N, we also have an array named MAP with size N that stores the state of ARR cells, ON for filled, OFF for empty, initially ARR is empty so every corresponding cell in MAP is set to OFF.

2. we keep the next empty cell index in a variable named NEXT, initially since ARR is empty, NEXT is set to 0. NEXT always point to the first index i in the array MAP such that MAP[i] is OFF, if any exists.

3. a function named add(element) always adds element into ARR at index NEXT, sets corresponding cell in MAP to ON.

4. a function named insert(element, index) adds element into ARR at index specified by user, sets corresponding cell in MAP to ON.

5. a function named delete(index) removes element from ARR at index specified by user, sets corresponding cell in MAP to OFF.

My question: How to update NEXT variable so it points to next empty cell index in ARR.

I know I can run a search on MAP from 0 to N and stop at the first occurrence of OFF and store its index as NEXT, but from what I read from online sources it has O(N) performance which is not great, I want to know if there are any better algorithms for this job or not, if not, can I design one myself? which books/online doc should I look into?

Thanks.

• Steven: Just to be more precise: should NEXT always point to the first index $i$ in the array MAP such that MAP[i] is OFF, if any?
• ErroR: Hi Mehdi, welcome to cs.stackexchange.com. If the running time is not important for you , when you insert new element, with linear time checking you can find the first empty cell of the array.
• Mahdi Baghbani: @Steven yes, you got it correct, one of my friends suggested that NEXT itself could be an array to hold several indexes, but we weren't sure about the algorithm so I asked it here.
• ErroR: Or it's sufficient to set the next to be element that deleted from the array (according to $delete(index)$ procedure). Or when you call the procedure $Add(element)$ you can find the first cell that empty before inserted element or after it. Finally when you call $ insert(element, index),ドル if $next=index$ you can act like that explained for procedure $Add(element)$.

Answer 1

I'm assuming that you're on a RAM machine with word size $\Theta(\log N$). Keep a van Emde Boas tree $T$ storing the empty positions (integers from 1ドル$ to $N$).

Whenever you insert an element $i$, delete $i$ from $T$ (in $O(\log \log N$) time) and set NEXT to the minimum element in $T$ (in $O(1)$ time).

Whenever you delete an element $i$, insert $i$ to $T$ and set NEXT to the minimum between the current values of NEXT and $i$.

This requires $O(\log \log N)$ time per operation but would require time $O(N \log \log N)$ to build the tree. To improve the construction time to $O(N)$ you can start with a tree containing only the index 1ドル$. Then during the first $N-1$ operations do the following: before the $i$-th operation is performed check if MAP[i+1]=OFF. If this is the case, then add $i+1$ to $T$. Proceed with the operation normally. This is taking advantage of the fact that, after the $i$-th operation is performed, we must necessarily have NEXT<=i+1.

You can't get much better solutions since you essentially need to solve the predecessor problem which admits a lower bound of $\Omega( \frac{\log \log N}{\log \log \log N})$ for a word size of $\Theta(\log N)$.

For a slower but easier to implement solution replace the van Emde Boas tree with an AVL tree. The initial tree can be built in $O(N)$ time (the keys are sorted) and each operation requires $O(\log N)$ time.

• Mahdi Baghbani: Thanks for the solution, I'll try to implement it into code, I just have a question, $O(N \log \log N)$ to build the tree is juts a 1 time operation right? or per every add, insert, delete I should construct the tree?
• Steven: The tree is constructed only once, at the same time when ARR and MAP are created and initialized.