Сортированная структура данных со случайным доступом

Question

Мне нужно реализовать саморазделенную структуру данных со случайным доступом. Есть идеи?

Answer 1

Самостоятельная сортировка немного противоречива. Прежде всего

Какая структура данных?

Есть много различных структур данных там, такие как:

• Связанный список
• Двусвязные список
• бинарное дерево
• Hash набор/карта
• Stack
• Куча

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

Теперь, не все из них могут или должны быть саморазделениями, такими как Стек, было бы странно, если бы это было саморазделение.

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

Для Linked Lists

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

Если вы хотите отсортировать после его вставки, т.е. в случайные моменты времени, а затем вы можете просто реализовать сортировку algororithm отличается от вставки рода, может быть, bubblesort или, может быть, quicksort, я бы избежать BubbleSort, хотя, это намного медленнее! Но легче задушить разум вокруг.

Random Access

Random всегда что-то вот время обсуждается вокруг так есть читать о том, как выполнить хорошую рандомизации и вы будете на своем пути, если у вас есть связанный список и есть «getAt» -метод, вы можете просто рандомизировать индекс между 0 и n и получить элемент в этом индексе.

Answer 2

Поддержание сортированного списка и доступа к нему произвольно требует не менее O (lgN)/операции. Итак, ищите AVL, red-black trees, treaps или любую другую подобную структуру данных и обогащайте их для поддержки случайной индексации. Я предлагаю treaps, так как они проще всего понять/реализовать.

Одним из способов обогащения дерева treap является сохранение в каждом узле количества узлов в поддереве, внедренных в этот узел. Вам нужно будет обновить счет при изменении дерева (например: вставка/удаление).

Answer 3

Я не слишком вовлечен в последнее время с реализацией структур данных. Вероятно, этот ответ не является ответом вообще ... вы должны увидеть «Введение в алгоритмы», написанные Томасом Корменом.В этой книге много «рецептов» с объяснениями о внутренней работе многих структур данных. С другой стороны, вы должны учитывать, сколько времени вы хотите потратить на составление алгоритма, размер ввода и если есть реальная необходимость специального вида структуры данных.

Answer 4

Само упорядоченная структура данных может быть двоичными деревьями поиска. Если вам нужна собственная сортированная структура данных и самобалансированная. Дерево AVL - это путь. Время поиска будет O (lgn) для случайного доступа.