How to create an insert in an infinite array

Question

Description of the problem

Imagine we have an infinite array where we store integers. If the elements n are in the array, only the first n cells are used, the rest are empty.

I am trying to find a data structure / algorithm capable of:

• check for item
• insert a new item if it is not already saved
• delete an item if it is saved

Each operation must be in O(sqrt(n)) .

Approach 1

I came across this site where the following algorithm was presented:

• An array (actually imagine this) divided into subarrays. Their length is 1, 4, 9, 16, 25, 36, 49, etc. The last subarray is not an ideal square - it cannot be completely filled.
• Suppose that considering these subarrays as sets, they are all fine. Thus, all the elements of the heap that are further to the right are larger than any element from the heaps to the left.
• Each such subarray represents a binary heap. Maximum heap.
• Search: go to the first heap indices (so again 1, 4, 9, 16, ...) and continue until you find that the first heap with the maximum value (max is stored on these indices) is greater than your number. Then check this submachine / heap.
• Paste: after performing the search, paste the item into the heap where it should be. When the heap is full - take the largest element and insert it into the next heap. And so on.

Unfortunately, this solution is O(sqrt(n) * log(n)) .

How to make it pure O(sqrt(n)) ?

Idea 2

Since all operations require a search, I believe the insert and delete will be O(1) . Just a hunch. And, perhaps, after the insert is completed, the deletion will be obvious.

Explanation

What does an infinite array mean?

Basically, you can store any number of elements in it. It is endless. However, there are two limitations. First, one cell can store only one item. The second - when the array currently stores n elements, only the first n cells can be used.

How about order?

It does not matter.

Answer 1

Did you consider a bicameral heap (aka: BEAP)?

The heap maintains the height of sqrt(n) , which means insert, find and delete everything in O(sqrt(n)) in the worst case.

These structures are described in a 1980 article by Munro and Suwanda Implicit data structures for quick retrieval and updating .

Answer 2

Create a linked list with a set of k arrays that represent hash tables.

According to the idea of ​​the first site, let the hash tables be 1, 4, 9, 16, 25, 36, 49, ... elements in size.

Thus, the data structure contains N=k*(k+1)*(2*k+1)/6=O(k^3) (this is the result of the well-known summation formula for adding squares) of elements with k hash tables.

Then you can sequentially search each hash table for elements. Hash validation, insertion, and deletion operations work in O(1) time (assuming a separate chain so that deletions can be processed correctly), and since k<sqrt(N) (actually less than the cubic root), this meets the requirements time of your algorithm.

If the hash table is full, add the sitelink in the linked list. If the hash table is empty, remove it from the list (add it if necessary later). Inserting / deleting a list is O(1) for a doubly linked list, so this does not affect the time complexity.

Note that this improves other answers that offer a direct hash table because rewriting is not required as the data structure grows.

Answer 3

I think approach 1 works, I just think some of the math is wrong.

The number of auxiliary arrays is not O(sqrt(n)) it O(cuberoot(n))

So you get O(log(n)*n^(1/3)) = O( (log(n) / n^(1/6)) * n^(1/2) ) , and with lim(log(n) / n^(1/6)) = 0 we get O( (log(n) / n^(1/6)) * n^(1/2) ) < O(sqrt(n))

My CS is a little rusty, so you have to double check it. Please let me know if I am wrong.

Answer 4

The short answer is that fulfilling all your requirements is not possible for the simple fact that the array is a representation of elements ordered by index; and if you want to save the first elements of n that are referenced by the first indices of n , as you say, any deletion may potentially require re-indexing (which moves the elements up the array) of the O(n) order of operations,

(However, ignoring deletion, this was my previous suggestion: since your array is infinite, you probably won't mind if I hide one of the rules a bit. Think about how your array looks like memory addresses on a computer, then create a balanced binary tree, sending a block of array elements for each node (I'm not too experienced with trees, but I believe that you will need a block of four elements, two for children, one for value, and one for height). Elements reserved for children will be just keep nach You can use 4n = O(n) instead of n space instead of n space (smoothing your rule a little) and it will be much more complicated since operations with BST will be O(log2 n) (instead of assigning element blocks to a node construct can also be done by dividing each element of the array into sections of bits, of which you are probably enough in a theoretically endless scenario.)

Answer 5

Since you are storing integers, just make an array of 4 billion ints. Then, when you add the increment element, the integer equal to the element is 1. You can add, delete, verify that the element takes O (1) time. This is basically just a hash table without a hash.