У меня есть набор объектов (большой rationals), что я буду обрабатывать. В каждом случае обработка будет состоять из удаления самого маленького объекта в наборе, выполнение некоторой работы и затем добавление 0-2 новых объектов (который всегда будет больше, чем удаленный объект). Набор будет инициализирован с одним объектом, и работа продолжится, пока это не будет пусто. Я не уверен, какого размера набор, вероятно, достигнет, но я ожидал бы в диапазоне объекты 1M-100M. Я не должен буду определять местоположение никакого объекта кроме самого маленького.
Я в настоящее время планирую использовать красно-черное дерево, которое возможно настраивают для хранения указателя на самый маленький объект. Однако я никогда не использовал тот прежде, и я не уверен, соответствует ли мой шаблон использования своим характеристикам хорошо.
1) Существует ли опасность шаблон удаления слева +, случайная вставка будет влиять на производительность, например, путем требования значительно более высокого количества вращений, чем случайное удаление было бы? Или удалит и вставит операции все еще быть O (зарегистрируйте n) с этим шаблоном использования?
2) Некоторая другая структура данных дала бы мне лучшую производительность, или из-за шаблона удаления или из-за использования в своих интересах факта, я только когда-либо должен находить самый маленький объект?
Обновление: довольный я спросил, двоичная "куча" является ясно лучшим решением для этого случая и, как обещано оказалась очень легкой реализовать.
Hugo
Двоичная куча бинарная куча гораздо лучше подходит для того, что вы хотите. Она проще в реализации и быстрее, поскольку вы заботитесь только о нахождении наименьшего элемента и вставках. Нахождение наименьшего элемента - O(1), удаление - O(log N), а вставка - также O(log N).
Куча даст вам O (1) удаление O (log n) и вставку O (log n), и это намного проще реализовать, чем красно-черное дерево
При необходимости хорошо знать, как создавать более сложные структуры данных. Однако, как правило, лучше всего начать как можно проще и использовать что-то более сложное только тогда, когда окажется, что это необходимо.
Единственный раз, когда я реализовал самобалансирующееся дерево, однажды я случайно узнал, что мое дерево будет действительно большим (более 10 000 элементов), а данные будут поступать отсортированными скачками. Это означало, что если бы я использовал обычное двоичное дерево, у меня получился бы почти связанный список.
Если ваши данные вводятся в случайном порядке, вам действительно не следует беспокоиться об алгоритме балансировки.