загуглил это дерево. Да уж, жесть, конечно там) Двоичное дерево поиска является чуть ли не тривиальной структурой по сравнению с деревьями, которые придуманы...
Проблемка. На value ведь никакого условия уникальности нет, верно? прикинь, надо удалить 2 минимальных, а у тебя с минимальным значением 4 элемента - ну и какие 2 из них удалять?
абсолютно точно подмечено!
на value нет никакого условия уникальности. Еще плохо то, что диапазон допустимых значений неизвестен, кроме того, что value > 0, т к это цена.
Как я понял из условия, программа должна обрабатывать наиболее ранние поступившие на обработку объекты (FIFO), поэтому при вставке объекта в отсортированный список дополнительно буду смотреть на index. Др.словами, будут удаляться снача те объекты, у которых index минимальный.
Итого. Очень вероятно, что здесь действительно, надо делать через R-tree, но это пока неподъемно).
Оставлю список + массив. Это приводит к тому, что удаление по индексу выполняется за О(1), удаление первых N элементов, ну тоже за О(1) (или это О(N) считается, не знаю точно) и все время будет тратиться в основном на вставку объекта в нужную позицию с сохранением упорядоченности.
Для одномерного массива будет выделен кусок памяти для 1 млн. элементов. Вроде массив будет легчайший (лишь указатель на элемент списка), но фрагментация может быть дичайшей + потребуется динамическое расширение размера массива со временем. Наверное, это некритично)
