Алгоритм сортировки коллекции при вставке в середину

Question

Допустим, у меня есть большая коллекция элементов.
Каждый элемент имеет поле «position», которое является положительным целым числом.
Никакие два элемента не имеют одинакового значения для поля «позиция».

Единственная поддерживаемая операция коллекции: addElement (newElement, positionAfterElement), где:
- newElement - новый элемент, который будет добавлен (его позиция пока неизвестна)
- positionAfterElement - это существующий элемент коллекции.

Функция гарантирует, что:
- position (positionAfterElement) - ни один другой элемент в коллекции не имеет позиции между позицией (positionAfterElement) и позицией (newElement)

Я могу изменить значение всех позиций элемента по своему желанию, но я хочу минимизировать количество изменений (в среднем).

Как мне реализовать функцию addElement?

Я мог бы просто сдвинуть все элементы с более высокими позициями на 1, но я почти уверен, что должен быть лучший способ сделать это.

Спасибо всем за помощь.

Answer 1

Используйте сбалансированное дерево. На каждом узле дерева ведите счетчик количества предметов под ним (left.count + right.count + 1). Затем вы можете легко вычислить индекс элемента при переходе к нему. Это O (n log n) время в количестве операций.

Answer 2

ОК, вот что я реализовал в псевдокоде:

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

Answer 3

Вот основная идея:

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.

расширение массива - дорогостоящая операция, но, поскольку она умножает размер массива, в среднем (если ваш ввод случайный, а не обработанный противником), вам придется делать эту операцию очень редко.

основным недостатком этого решения является то, что вам придется остерегаться переполнения int ....