Поддержание сортировки при смене случайных элементов
Я столкнулся с этой проблемой, где мне нужно эффективно удалить наименьший элемент в списке / массиве. Это было бы довольно тривиально решить - достаточно было бы кучи.
Однако теперь проблема заключается в том, что при удалении наименьшего элемента это приведет к изменениям в других элементах структуры данных, что может привести к изменению порядка. Пример таков:
У меня есть массив элементов:
[1,3,5,7,9,11,12,15,20,33]
Когда я удаляю "1" из массива, "5" и "12" меняются на "4" и "17" соответственно.
[3,4,7,9,11,17,15,20,33]
И, следовательно, порядок не поддерживается.
Однако удаляемый элемент будет иметь указатели на все элементы, которые будут изменены, но неизвестно, сколько элементов будет изменено и на сколько.
Итак, мой вопрос:
Каков наилучший способ хранения этих элементов для максимизации производительности при удалении наименьшего элемента из структуры данных при сохранении сортировки? Или я должен просто оставить это не отсортированным?
Моя текущая реализация просто хранит их несортированными в векторе, поэтому сложность по времени составляет O(N^2), O(N) для поиска наименьшего элемента и N удалений.
2 ответа
A.
Если у вас есть список M всех измененных элементов упорядоченного списка L,
пройти через М, и для каждого элемента
Если он все еще заказан со своими соседями в М, живи так и будет.
Если это не в порядке с соседями, исключите его из М.
Такие исключенные элементы создадут список N
Заказ N
Используйте некоторый алгоритм для объединения упорядоченных списков. http://en.wikipedia.org/wiki/Merge_algorithm
B.
Если вы уверены, что новых элементов мало и они не сильно изменены, просто используйте пузырьковую сортировку.
Я бы все равно пошел с кучей, подкрепленной массивом
В случае, если после каждого всплывающего окна изменяется только несколько элементов, После выполнения операции всплывающего окна выполните динамическое наращивание / понижение для любого элемента, значение которого уменьшается. Он по-прежнему будет в порядке значений O(nlog k), где k - это размер вашего массива, а n - количество элементов, размер которых уменьшился.
Если размер элементов изменяется по размеру, вы можете рассматривать это как случай, когда у вас есть несортированный массив, и вы просто создаете кучу из массива.