Algorithm to keep collection sorted while inserting in the middle

Question

Let's say I have a large collection of elements.
Each element has a "position" field, which is a positive integer.
No two elements have the same value for the field "position".

The only supported operation of the collection is: addElement(newElement, positionAfterElement), where:
- newElement is the new element to be added (its position is unknown for now)
- positionAfterElement is an existing element of the collection.

The function will guarantee that:
- position(positionAfterElement) < position(newElement)
- no other element in the collection has a position between position(positionAfterElement) and position(newElement)

I can change the value of all the element positions as I wish but I want to minimize the number of changes (on average).

How should I implement the addElement function?

I could just push all the elements with higher positions by 1 but I am pretty sure there must be a better way to do this.

Thanks all for your help.

Answer 1

Here's a basic idea:

expected_number_of_elements = 10^6
spread_factor = 100
first element gets position = spread_factor * expected_number_of_element
each following element inserted:
    if its inserted in last position, give it the last element's position + spread_factor
    if its inserted in the first position, give it the first element's position - spread_factor
    otherwise, put it in the middle between its 2 closest neighbors
    if you don't have any space left: expand_the_array


expand_the_array:
    spread_factor = spread_factor * 10
    iterate over all the elements, and multiply position by 10.

expanding the array is an expensive operation, but since it multiplies the size of the array, on average (assuming your input is random, and not crafted by an adversary) you'll have to do this operation very rarely.

the major drawback of this solution, is that you'll have to watch out for int overflow....

Answer 2

Use a balanced tree. At every node of the tree, keep a count of the number of items below it (left.count + right.count + 1). Then, you can compute the index of an item easily while traversing to it. This is O(n log n) time in the number of operations.

Answer 3

OK, so here is what I implemented, in pseudo-code:

addElement(newElement, positionAfterElement):
    p0 <- positionOf(positionAfterElement)
    c <- 5
    finished <- false
    while (not finished):
        search for all elements which positions are in the range [p0 + 1, p0 + c]
        if there are less than c elements in that range:  // the range is not full
            adjust position of elements in the range, and position of newElement,
            so that
              - elements are correctly ordered
              - element positions are "evenly spread out" within the range
            finished <- true
        else:                                             // the range is full
            c <- c * 2
    end while
end addElement