Невозможно добавить категорию в AVAudioPlayer

Хорошо. Я думаю, что у меня есть ответ, который дает вам все эти операции в amortized O (1), что означает, что любая операция может занимать до O (n), но любая последовательность n операций принимает O (1) время за операцию .

Идея состоит в том, чтобы хранить ваши данные как декартово дерево . Это двоичное дерево, подчиняющееся свойству min-heap (каждый узел не больше его дочерних элементов) и упорядочен таким образом, что обход узлов по порядку возвращает вам узлы в том же порядке, в котором они были добавлены. Например, здесь представлено декартово дерево для последовательности 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

. Можно вставить элемент в декартово дерево в O (1) амостатированное время, используя следующую процедуру. Посмотрите на правый позвоночник дерева (путь от корня до самого правого листа, образованный всегда, идя вправо). Начиная с самого правого узла, сканируйте вверх по этому пути, пока не найдете первый узел меньше узла, который вы вставляете. Измените этот узел так, чтобы его правый дочерний элемент был этим новым узлом, затем сделайте прежний правый дочерний узел этого левого дочернего узла только что добавленного узла. Например, предположим, что мы хотим вставить другую копию 2 в указанное выше дерево. Мы поднимаемся по правому корешку мимо 5 и 3, но останавливаемся ниже 1, потому что 1 & lt; 2. Затем мы изменим дерево так, чтобы оно выглядело так:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Обратите внимание, что обход по порядку дает 2 1 4 3 5 2, который представляет собой последовательность, в которую мы добавили значения.

Это выполняется в амортизированном O (1), потому что мы можем создать потенциальную функцию, равную числу узлов в правом разрезе дерева. Реальное время, необходимое для вставки узла, равно 1 плюс количество узлов в рассматриваемом нами позвоночнике (назовем это k). Как только мы найдем место для вставки узла, размер спинного хребта сократится на длину k - 1, так как каждый из k узлов, которые мы посетили, больше не находится справа от позвоночника, а новый узел находится на своем месте. Это дает амортизированную стоимость 1 + k + (1 - k) = 2 = O (1) для амортизированной вставки O (1). В качестве другого способа думать об этом, как только узел был удален с правого позвоночника, он никогда не будет частью правого позвоночника, и поэтому нам больше не придется его перемещать. Поскольку каждый из n узлов может перемещаться не более одного раза, это означает, что n вложений может выполнять не более n ходов, поэтому общая продолжительность выполнения не превышает O (n) для амортизированного O (1) на элемент.

Чтобы сделать шаг dequeue, мы просто удалим самый левый узел из декартового дерева. Если этот узел - лист, мы закончили. В противном случае узел может иметь только один дочерний элемент (правый ребенок), и поэтому мы заменяем узел его правым дочерним элементом. При условии, что мы отслеживаем, где находится самый левый узел, этот шаг занимает время O (1). Однако после удаления самого левого узла и его замены его правым дочерним элементом мы можем не знать, где находится новый крайний левый узел. Чтобы исправить это, мы просто ходим по левому позвоночнику дерева, начиная с нового узла, который мы только что переместили в самый левый ребенок. Я утверждаю, что это все еще работает в O (1) амортизированном времени. Чтобы убедиться в этом, я утверждаю, что узел просматривается не более одного раза во время любого из этих проходов, чтобы найти самый левый узел. Чтобы увидеть это, обратите внимание на то, что после того, как узел был посещен таким образом, единственный способ, который нам когда-либо понадобится, посмотреть на него снова, будет, если бы он был перемещен из дочернего элемента самого левого узла в самый левый узел. Но все узлы, которые были посещены, являются родителями самого левого узла, поэтому этого не может быть. Следовательно, каждый узел посещается не более одного раза во время этого процесса, а pop работает в O (1).

Мы можем найти find-min в O (1), потому что декартово дерево дает нам доступ к наименьший элемент дерева бесплатно; это корень дерева.

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

Короче говоря, мы получаем O (1) амортизируется push и pop, а O (1) наихудший поиск-мин.

Если я смогу придумать реализацию O (1) наихудшего варианта, я обязательно опубликую его. Это была большая проблема; спасибо за публикацию!