Очередь со вставкой в середину

Нужна структура с тремя операциями:

• добавить элемент в конец;
• забрать элемент из начала;
• вставить элемент в середину.

Первые две умеет любая очередь. Третья убивает все стандартные контейнеры: у vector, deque и list вставка в середину стоит линию — надо либо сдвигать элементы, либо дойти до середины по указателям.

Хочется $O(1)$ на операцию.

Идея

Держим не одну структуру, а две — a и b, — и поддерживаем инвариант:

$$|a| = |b| \quad \text{или} \quad |a| = |b| + 1$$

То есть при $2n$ элементах в каждой половине по $n$, при $2n+1$ — в первой $n+1$, во второй $n$. Логическая последовательность — это a, за которой идёт b, а «середина» — граница между ними.

Тогда каждая из трёх операций становится парой действий по краям.

Разбор по случаям

Пусть сейчас $|a| = |b| = n$ (чётное число элементов):

• вставить в середину — положить в конец a. Стало $n+1$ и $n$, инвариант выполнен.
• вставить в конец — положить в конец b, стало $n$ и $n+1$; перенести первый элемент b в конец a.
• забрать из начала — снять с начала a, стало $n-1$ и $n$; перенести первый элемент b в конец a.

Пусть теперь $|a| = n+1$, $|b| = n$ (нечётное):

• вставить в середину — положить в начало b. Стало $n+1$ и $n+1$.
• вставить в конец — положить в конец b. Стало $n+1$ и $n+1$.
• забрать из начала — снять с начала a. Стало $n$ и $n$.

Нужны операции: добавить в конец, добавить в начало, снять с начала. Все три есть у deque за $O(1)$.

Код

Вместо шести отдельных веток проще написать одну функцию восстановления баланса:

struct MidQueue {
    deque<int> a, b;                     // инвариант: |a| == |b| или |a| == |b| + 1

    void rebalance() {
        while (a.size() > b.size() + 1) { b.push_front(a.back()); a.pop_back(); }
        while (b.size() > a.size())      { a.push_back(b.front()); b.pop_front(); }
    }
    void pushBack(int x)      { b.push_back(x);  rebalance(); }
    void insertMiddle(int x)  { a.push_back(x);  rebalance(); }
    int  popFront()           { int x = a.front(); a.pop_front(); rebalance(); return x; }

    size_t size() const { return a.size() + b.size(); }
};

Каждый цикл в rebalance делает не больше одного шага: инвариант нарушается ровно на единицу. Поэтому операция стоит $O(1)$, а не амортизированную константу.

Проверено: 20 000 случайных сценариев по 60 операций; на каждом шаге содержимое, длина и баланс сверялись с эталонным vector.

Где ошибиться

Что считать серединой. При чётном числе элементов вставка «в середину» делает новый элемент $(n+1)$-м из $2n+1$. При нечётном — тоже ровно посередине. В коде это выражается тем, что после вставки всегда $|a| = \lceil k/2 \rceil$, где $k$ — новый размер. Если в условии середина определена иначе, меняется одна строка, но проверять надо явно: расхождение на единицу здесь ловится только тестами.

insertMiddle в нечётном случае кладёт в начало b, а не в конец a. В коде выше это получается само: a.push_back нарушает баланс на единицу, и rebalance тут же переносит элемент в начало b. Записанное явно по случаям, это две разные ветки.

Общий приём

Пара структур с поддерживаемым балансом — стандартный ход, когда операция не выражается через края одной структуры.

Так же устроена очередь на двух стеках: недостающий конец берётся из второй структуры. Так же работает пара куч для поддержания медианы: меньшая половина в максимум-куче, большая в минимум-куче, размеры отличаются не больше чем на единицу.

Признак, по которому приём узнаётся: нужна точка внутри последовательности, а контейнеры дают доступ только к краям. Разрежьте последовательность в этой точке и держите две части отдельно.