# I dreamt of a data structure, does it exist?

I haven't managed to find this data structure, but I'm not an expert in the field.

The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):

An array of length 1 is a merge-array.

An array of length 2^n (for n > 0) is a merge-array iff:

• the first half is a merge-array and the second half is empty or
• the first array is full and sorted, and the second half is a merge-array.

Note that if the array is full, it is sorted.

To insert an element, we have two cases:

• If the first half is not full, insert recursively in the first half.
• If the first half is full, insert recursively in the second half.
• After the recursive step, if the whole array is full, merge the halves (which are sorted), and resize it to the double of its original length.

To find an element, recurse in both halves, using binary search when the array is full. (This should be efficient since there are at most $O(\log(n))$ ascending fragments).

The structure can be thought as a static version of mergesort.

It's not clear what one should do to erase an element.

Edit: after improving my understanding of the structure.

• You defined it, therefore it exists. I think you have to smooth out some points, though. First, invariant #2 confuses me as it does does not seem to apply to intermediate states as you describe them. Second, what do you do when elements are removed? – Raphael Aug 6 '11 at 16:12
• You dreamt up a data structure, not dreamt of it... – Andrej Bauer Aug 7 '11 at 7:13
• @Raphael Thanks for your comments, I improved the definition following your thoughts. I didn't think of an algorithm for removal, I just wanted to check if this structure was in the literature before dedicating more time to it (and couldn't find anything in Google). On your first sentence, you can define God, but does it exist? :) – pbaren Aug 7 '11 at 7:22
• @Andrej Thanks, English is not my native language. (I guess it's not yours either :) – pbaren Aug 7 '11 at 7:23
• @Andrej: the OP originally had "dreamt with", which is almost certainly not what was meant. I changed it to "of" instead of "up". Both are correct grammatically, but both also change the meaning. "Of" was the more interesting sounding option... – András Salamon Aug 7 '11 at 18:57

You're describing the classical Bentley-Saxe logarithmic method, applied to static sorted arrays. The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem. (A search problem is decomposable if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.) The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor. Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.

These notes cover the basics.

Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.

• Those are beautifully written and illustrated notes, and I have used them as a reference many times. Thanks for making them available! – jbapple Aug 6 '11 at 22:04
• I see how shuttle trees (from the first half of the paper introducing cache oblivious lookahead arrays) are related to vEB trees, but what is the relationship between COLAs and vEB trees? – jbapple Aug 6 '11 at 22:07
• Thanks, this material seems a very interesting generalization of the idea. I have always thought that data structures are frozen algorithms, which you can run step by step, but I had never found a useful formalization of that intuition. – pbaren Aug 7 '11 at 7:27
• Did the first link work for anyone else? – A T Mar 5 '12 at 17:05
• Yes, I just tried it. (Unfortunately, it goes to an Elsevier paywall; sorry!) – Jeffε Mar 5 '12 at 20:31

This is similar to a log-structured merge trees or cache oblivious lookahead arrays (or COLAs).

The simplest COLA is an array of size $2^k-1$ with virtual "levels" of length $2^i$ for $0 \leq i < k$ laid out in order in the array. Each level is totally full or totally empty, and each level is sorted.

To insert an item, place it it level 0 (with $2^0$ length) if level 0 is empty. Otherwise, merge it with the item at level 0 and fill level 1 (with $2^1$ length) with the resulting list of length 2. If level 1 is already full, merge again; repeat.

Insert takes $O(\lg n)$ amortized / $O(n)$ worst-case time. Lookup takes $O(\lg^2 n)$ time. More advanced versions can reduce and partially deamortize these.