Самая быстрая структура данных для вставки / сортировки

Question

Мне нужна структура данных, которая может вставлять элементы и сортировать себя как можно быстрее. Я буду вставлять гораздо больше, чем сортировка. Удаление - не большая проблема, и нет места. Моя конкретная реализация будет дополнительно хранить узлы в массиве, поэтому поиск будет O (1), т. Е. Вам не нужно об этом беспокоиться.

Answer 1

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

_{¹ Если подумать, есть второй недостаток.Если вы недооцените частоту сортировки, это может в конечном итоге оказаться медленнее, чем дерево или отсортированный список.Например, если вы сортируете после каждой вставки, цикл вставки + быстрой сортировки будет плохой идеей.}

Answer 2

Просто используйте одно из самобалансированных бинарных деревьев поиска , например, красно-черное дерево.

Answer 3

Используйте любое из сбалансированных бинарных деревьев, таких как деревья AVL.Это должно дать O (LG N) сложность времени для обеих операций, которые вы ищете.

Answer 4

Если вы можете сделать много вставок перед каждой сортировкой, то, очевидно, вы должны просто добавить элементы и отсортировать не раньше, чем вам нужно. Мой фаворит - сортировка слиянием. То есть O (N * Log (N)), хорошо себя ведет и имеет минимум манипуляций с хранилищем (new, malloc, балансировка дерева и т. Д.)

* 1002. индекс. Затем вы просто сканируете весь массив и собираете индексы, ИСТИНА.

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

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

Answer 5

Если вам не нужен произвольный доступ к массиву, вы можете использовать Heap .

Наихудшая и средняя сложность времени:

• Вставка O (log N)
• O (1) считывание наибольшего значения
• O (log N)) для удаления наибольшего значения

Может быть перенастроен, чтобы выдавать наименьшее значение вместо наибольшего.Повторно удаляя наибольшее / наименьшее значение, вы получаете отсортированный список в O (N log N).

Answer 6

У меня был хороший опыт для такого рода задач с использованием Пропустить список

По крайней мере, в моем случае это было примерно в 5 раз быстрее, чем сначала добавлять все в список, а затем выполнять сортировку по нему в конце.