Вот такое условие. На вход программе подаются однотипные объекты (будем называть их T), обладающих только 2мя свойствами:
index (натуральное уникальное число, стартующее с 1 и увеличивающееся на +1)
value (дробное положительное значение, диапазон неизвестен)
то есть на вход программе подаются объекты T(index, value). Количество может быть большим (насколько неизвестно, но большим)).
У пользователя есть такие команды:
1. удалить N первых минимальных по value объектов. Другими словами, например, если N = 3, то надо удалить 3 объекта, имеющих наименьшее значение value.
2. удалить ЛЮБОЙ объект по полю index.
Вот пример входных данных из 5ти объектов Т: T(1, 23.3), T(2, 17.3), T(3, 129.5), T(4, 55.0), T(5, 24.8)
----------------------------------------------------
И вот что-то прикурил я здесь по применению оптимальных структур данных, т к есть проблемки...
Коротко мои мысли.
1. Если входные объекты сразу не вставлять в отсортированное пространство по полю value, то удаление N первых минимальных сведется к циклам, т к местоположение наименьших будет хаотичным. Следовательно, при поступлении очередного объекта Т его надо сразу засовывать в нужную позицию отсортированного пространства. Какую структуру данных использовать? Дерево поиска? Не катит вроде вообще. Вижу список, ну, наверное, двусвязный. При поступлении очередного объекта Т придется найти его позицию вставки, это вроде сложность O(K/2), где К - длина списка. Разве не так? Имея такой список удаление N мин.по value объектов будет равносильно удалению из начала списка N объектов.
2. Но список из п1 не годится для операции №2 (удаление по индексу), т к список отсортирован по value и тогда операция удаления будет сводится к фул-скану. Завести динамический массив, у которого индекс+1 равен index объекта Т. Значением элементов такого массива будет ссылка на объект, хранящийся в отсортированном двусвязном списке. При такой организации удаление будет выполнять за время О(1) (или близкое к нему). Но проблема здесь в том, что с течением времени будет возникать фрагментация (будут образовываться пустоты, разреженность). Также неизвестно кол-во входных объектов Т, поэтому хз каким размером нужно делать этот массив.
Здесь, возможно, вообще надо уходить в хеш-таблицы с цепочками, но по условии не говорится о диапазоне поля value (хотя может для хеш это и не важно).
Вопрос: структуры данных, которые я хочу пока что применить (двусвязный список + дин.массив со ссылкой на элемент списка, по факту индекс, как в БД) они нормально подходят для такой задачи или здесь вообще все совсем по-другому, вот в корне все по-другому??
спс. за внимание
Добавлено
Еще допишу такой момент. Пользователь достаточно часто вызывает команду №1 и реже команду №2 (в 2-3 реже, чем команду №1).
