Сохраняющая ранг структура данных, отличная от std:: vector?
Я столкнулся с приложением, в котором мне нужно спроектировать контейнер, который имеет произвольный доступ (или, по крайней мере, лучше, чем O(n)), имеет недорогие (O(1)) вставки и удаления, и сохраняет данные в соответствии с порядком (рангами).) указано при вставке.
Например, если у меня есть следующий массив:
[2, 9, 10, 3, 4, 6]
Я могу вызвать удаление по индексу 2, чтобы удалить 10, и я также могу вызвать вставку по индексу 1, вставив 13.
После этих двух операций у меня будет:
[2, 13, 9, 3, 4, 6]
Числа хранятся в последовательности, и для операций вставки / удаления требуется индексный параметр, чтобы указать, куда нужно вставить номер или какой номер следует удалить.
У меня вопрос: какие структуры данных, помимо связанного списка и вектора, могут поддерживать что-то подобное? Я склоняюсь к куче, которая имеет приоритет над следующим доступным индексом. Но я видел кое-что о полезности Fusion Tree (но больше в теоретическом смысле).
Какие структуры данных дадут мне наиболее оптимальное время работы при сохранении потребления памяти? Я играл с хеш-таблицей, сохраняющей порядок вставки, но до сих пор она не удалась.
Причина, по которой я выбрасываю использование std:: vector прямо, заключается в том, что я должен создать что-то, что превосходит вектор в терминах этих базовых операций. Размер контейнера может увеличиться до сотен тысяч элементов, поэтому о сдвигах в std:: vector не может быть и речи. Те же самые проблемные строки со связанным списком (даже если он связан дважды), при переходе к указанному индексу в худшем случае потребовалось бы O (n/2), который округляется до O (n).
Я думал о двойном связанном списке, который содержал указатель "Голова", "Хвост" и "Средний", но я чувствовал, что он не будет намного лучше.
2 ответа
В основном, чтобы иметь возможность вставлять и удалять в произвольной позиции, вы можете использовать связанные списки. Они позволяют O(1) вставить / удалить, но только при условии, что вы уже нашли позицию в списке, куда вставить. Вы можете вставить "после заданного элемента" (то есть, учитывая указатель на элемент), но вы не можете так же эффективно вставить "по заданному индексу".
Чтобы иметь возможность вставлять и удалять элемент по его индексу, вам потребуется более продвинутая структура данных. Существуют как минимум две такие структуры, о которых я знаю.
Одним из них является структура веревки, которая доступна в некоторых расширениях C++ ( SGI STL или в GCC через #include <ext/rope>). Это позволяет для O(log N) вставить / удалить в произвольной позиции.
Другой структурой, допускающей вставку / удаление O(log N), является неявный треп (неявное декартово дерево), некоторую информацию можно найти по адресу http://codeforces.com/blog/entry/3767, Treap с неявными ключами или https://codereview.stackexchange.com/questions/70456/treap-with-implicit-keys.
Неявный treap также может быть изменен, чтобы позволить находить в нем минимальное значение (а также поддерживать гораздо больше операций). Не уверен, может ли веревка справиться с этим.
UPD: На самом деле, я предполагаю, что вы можете адаптировать любое O(log N) двоичное дерево поиска (например, AVL или красно-черное дерево) для вашего запроса, преобразовав его в схему "неявного ключа". Общая схема такова.
Представьте себе двоичное дерево поиска, которое в каждый данный момент хранит последовательные числа 1, 2, ..., N в качестве своих ключей (N - количество узлов в дереве). Каждый раз, когда мы меняем дерево (вставляем или удаляем узел), мы пересчитываем все сохраненные ключи, чтобы они все еще были от 1 до нового значения N. Это позволит вставлять / удалять в произвольной позиции, поскольку ключ теперь является позицией, но это потребует слишком много времени для обновления всех ключей.
Чтобы избежать этого, мы не будем явно хранить ключи в дереве. Вместо этого для каждого узла мы будем хранить количество узлов в его поддереве. В результате, всякий раз, когда мы идем от корня дерева вниз, мы можем отслеживать индекс (позицию) текущего узла - нам просто нужно сложить размеры поддеревьев, которые у нас есть слева. Это позволяет нам при заданном k найти узел, имеющий индекс k (то есть k-й в стандартном порядке бинарного дерева поиска), за O(log N) время. После этого мы можем выполнить вставку или удаление в этой позиции, используя стандартную процедуру двоичного дерева; нам просто нужно обновить размеры поддерева всех узлов, измененных во время обновления, но это легко сделать за O(1) времени на каждый измененный узел, поэтому общее время вставки или удаления будет O(log N), как в оригинальное двоичное дерево поиска.
Таким образом, этот подход позволяет вставлять / удалять / получать доступ к узлам в заданной позиции за O(log N), используя любое O(log N) двоичное дерево поиска в качестве основы. Конечно, вы можете хранить дополнительную информацию ("значения"), которая вам нужна, в узлах, и вы даже можете рассчитать минимум этих значений в дереве, просто сохранив минимальное значение поддерева каждого узла.
Однако вышеупомянутые трэп и веревка являются более продвинутыми, поскольку они также допускают операции разделения и слияния (взятие подстроки / подмассива и объединение двух строк / массивов).
Рассмотрим список пропусков, который может реализовывать операции линейного временного ранга в своем "индексируемом" варианте.
Алгоритмы (псевдокод) см. В "Поваренной книге списка пропусков" Пью.
Может случиться так, что к методу дерева двоичного поиска "неявный ключ", описанному выше @Petr, проще добраться, и он может даже работать лучше.