27
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 5
    $\begingroup$ 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? $\endgroup$
    – Raphael
    Aug 6, 2011 at 16:12
  • 7
    $\begingroup$ You dreamt up a data structure, not dreamt of it... $\endgroup$
    – Andrej Bauer
    Aug 7, 2011 at 7:13
  • $\begingroup$ @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? :) $\endgroup$
    – pbaren
    Aug 7, 2011 at 7:22
  • $\begingroup$ @Andrej Thanks, English is not my native language. (I guess it's not yours either :) $\endgroup$
    – pbaren
    Aug 7, 2011 at 7:23
  • 3
    $\begingroup$ @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... $\endgroup$
    – András Salamon
    Aug 7, 2011 at 18:57

2 Answers 2

Reset to default
31
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ Those are beautifully written and illustrated notes, and I have used them as a reference many times. Thanks for making them available! $\endgroup$
    – jbapple
    Aug 6, 2011 at 22:04
  • $\begingroup$ 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? $\endgroup$
    – jbapple
    Aug 6, 2011 at 22:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – pbaren
    Aug 7, 2011 at 7:27
  • $\begingroup$ Did the first link work for anyone else? $\endgroup$
    – A T
    Mar 5, 2012 at 17:05
  • 1
    $\begingroup$ The link to the note breaks and probably should be replaced by jeffe.cs.illinois.edu/teaching/datastructures/notes/… $\endgroup$
    – Hsien-Chih Chang 張顯之
    Nov 26, 2018 at 18:11
11
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.