структуры данных — Реализация индексируемых списков пропусков в Stack Overflow
Все реализации списка пропусков, которые я обнаружил, используют ключи и связывают их со значениями.
Но мне нужен пропущенный список, где я могу вставить значение в индексную позицию i, чтобы все значения, следующие за этим
Индекс я могу быть запрошен с индексом, увеличенным на единицу.
вот небольшой пример для уточнения:
//pseudocode
//let skipList sk be a list of ints, containing 5 elements.
//insert 6 at index 3
sk.insert(3, 6);
//insert 5 at index 3
sk.insert(3, 5);
//get index 4
int value = sk.get(4);
сейчас value должно быть 6, потому что 5 был вставлен в индекс 3, поэтому значение 6 переместилось на один индекс вверх.
можно построить такую структуру данных, используя список пропусков, см.
Индексируемый скиплист здесь:
http://en.wikipedia.org/wiki/Skip_list
но я не смог найти реализацию. было бы очень полезно иметь такую структуру данных, например, в ситуациях, когда у вас есть много случайных вставок и доступ к большим спискам.
Решение
На странице википедии, которую вы разместили, есть ссылка на реализацию:
http://code.activestate.com/recipes/576930/
Это питон, хотя.
В качестве альтернативы возьмите существующую реализацию C ++, добавьте к ней ширину ссылок и реализуйте индексированный поиск.
Другие решения
Я реализовал в Sk # класс skiplist, у которого есть метод, который возвращает k-ое наибольшее значение в коллекции. Это именно то, что вам нужно для вашего get метод.
Однако метод вставки не указывает позицию, поскольку он всегда сохраняет список отсортированным, поэтому позиция определяется путем поиска среди существующих значений.
Взгляни на https://github.com/htoma/algorithms/blob/master/Algorithms/Algorithms/Sources/SkipLists/SkipList.cs, метод FindKLargestElement