Эффективно упорядоченная структура данных, поддерживающая дубликаты ключей

Я ищу структуру данных, которая эффективно упорядочивает объекты при вставке. Я хотел бы упорядочить эти объекты (в данном случае особи) на основе значения определенной переменной (в данном случае фитнес).

Структура данных должна допускать дублирование ключей, поскольку конкретное значение фитнеса может встречаться у разных особей. Это проблема, поскольку, например, структура данных TreeMap не допускает дублирования ключей. Я бы предпочел использовать этот тип древовидной структуры из-за ее эффективности O(log N).

Если бы я вставлял индивидуумы в упорядоченный список, эффективность упала бы до O(n), а сортировка индивидуумов после их вставки тоже была бы не очень эффективной.

Существует ли структура данных, которая была бы эффективной, сохраняла упорядоченность индивидуумов и поддерживала дублирование ключей?

Я буду очень часто добавлять и удалять записи после создания структуры данных, поэтому сортировка объектов после создания структуры будет очень дорогой.