Реализация структуры данных, поддерживающей различные операции

Question

Я должен реализовать структуру данных, которая поддерживает следующие три функции. Данные представляют собой пару (a, b) двух двойных значений и данные сосредоточены в конкретной области. Скажем, со значениями 'a' в диапазоне 500-600.

1. Вставить (double a, double b) - Вставить данные, пару (двойную, двойную) в структуру данных. Если первый элемент пары уже существует, обновите его второй элемент до нового значения.

2. Удалить (double a) - Удалить данные, содержащие первый элемент = a.

3. PrintData (int count) - печать значения данных с наибольшим значением count. Значение сравнивается по данным. Первое.

Вводный файл содержит ряд операций Insert, Delete и PrintData. В настоящее время я реализовал структуру данных как сбалансированное по высоте дерево двоичного поиска с использованием STL-Map, но это недостаточно быстро.

Есть ли другая реализация, которая быстрее, чем карта. Мы можем использовать кеширование для хранения наиболее распространенных запросов PrintData.

Answer 1

Я рекомендую 2 бинарных деревьев поиска (BSTs) - одна будучи карта от a до b (отсортированный по a), другие должны быть отсортированы по b.

Вторым должен быть пользовательский BST - вам нужно, чтобы каждый узел хранил счетчик количества узлов в поддереве с ним как root - эти подсчеты могут быть обновлены в O (log n), и позволит запросам O (log n) получить k-й наибольший элемент.

При выполнении вставки вы просто сначала посмотрите значение b в первом BST, затем удалите это значение из второго, затем обновите первое и вставьте новое значение во второе.

Для удаления вы просто будете искать значение b в первом BST (и удалить эту пару), а затем удалить это значение из второго.

Все упомянутые операции должны принимать O (log n).

Кэширование

Если вы, к примеру, только собираетесь запросить верхние 10 элементов, можно поддерживать другой BST, содержащий только те 10 элементов (или даже просто необязательно, отсортированный массив, так как есть только 10 элементов), которые мы затем запросим вместо второго BST выше.

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

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

Это приведет к запросу O (1) в наилучшем случае (наихудший вариант O (log n)), в то время как другие операции будут по-прежнему равны O (log n).

Хотя добавленная сложность, вероятно, не стоит того - O (log n) довольно быстро, даже для большого n.

Основываясь на этой идее, мы могли бы только есть этот маленький BST вместе с отображением BST a в b - это потребовало бы, что мы проверяем все значения, чтобы найти нужные из них во время выполнения запроса после удаления, так что это будет только действительно выгодно, если нет большого количества изъятий.

Answer 2

Я бы порекомендовал indexed skip list. Это даст вам O (log n) вставить и удалить, а O (log n) получит доступ к n наибольшему значению (при условии, что вы поддерживаете список в порядке убывания).

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

original skip list paper.