Какой класс коллекции лучше всего подойдет для хранения списка элементов, которые нужно отсортировать?

Для хранения списка элементов, которые нужно отсортировать, наилучшим выбором будет класс ArrayList или LinkedList. Оба класса являются реализациями интерфейса List, который позволяет хранить элементы в определенном порядке и обеспечивает удобный доступ к элементам по индексу. 

Для реализации механизма обновления объектов списка так, чтобы сначала обновлялись те, которые дольше всего не обновлялись, можно использовать специализированную структуру данных, например, PriorityQueue, которая позволяет хранить элементы в порядке их "приоритета". В каждом элементе списка можно хранить время последнего обновления объекта, а затем использовать PriorityQueue для выбора элементов для обновления в соответствии с временем последнего обновления.

Для хранения объектов с временем их последнего обновления также можно использовать ConcurrentSkipListMap, который представляет собой отсортированную коллекцию данных, обеспечивающую эффективный доступ по ключу и поддерживающую синхронизацию для многопоточного доступа. Однако, необходимо учитывать, что ConcurrentSkipListMap требует больше ресурсов и может не быть оптимальным выбором для определенных сценариев использования.

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

Достаточно списка. При принудительном обновлении берите первый элемент из списка. При любом обновлении перемещайте объект(ы) в конец. Можно перед началом из списка элемент удалить, а после конца в конце вернуть. 
 
 Тут вам еще понадобится какая-то структура, чтобы по объекту получить итератор на него в списке. Если у вас объекты каким-то id определяются, то это может быть 
std::unordered_map<int, std::list<Object>::iterator>
 . 
 
 Вам нужен какой-то потокобезопасный список, да. Доставать из списка первые 4 элемента можно и циклом, по одному. Операция быстрая. Или пусть каждый поток сам достает из списка первый элемент, лоча для этого список. 
 
 А вообще, есть и Lock-free списки. Если у вас обновления сами по себе очень быстрые операции, то такая структура может быть в итоге работать быстрее. 
 
 Edit: простите за C++-ый код. Не заметил, что вопрос с java тегом. В общем, тут нужны какой-то список и hashmap из id в итераторы в этом листе.