Очередь приоритетов Java

Question

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

C++ STL мультикарта имеет ту же функциональность, но O(1) сложность поиска и удаления элемента min (начать и стереть).Есть ли эквивалент в Java?

Answer 1

Коллекции Google предоставляет реализацию Multimap.В частности, TreeMultimap может использовать компараторы для сортировки на основе ключей, значений или того и другого.

Answer 2

Попробуйте Коллекции Apache Commons.

MultiHashMap и MultiValueMap (ссылки на эту страницу) фактически реализуют интерфейс.

На самом деле есть Приоритетная очередь там тоже есть, но он обесценился в пользу буферный пакет.

Answer 3

Во-первых, я бы проверил, что мультикарта C++ действительно дает O(1) для удаление минимальный элемент.Наиболее распространенными структурами для карт sotred/очередей приоритетов являются древовидные структуры, в которых запрос минимальный элемент имеет сложность O (1), но удаление это O(log n).

Тем не менее, я думаю, что список пропуска (реализованный в языке Java) ConcurrentSkipListMap) мощь дайте вам O (1) для удаления минимального элемента, но я не совсем уверен.Одна из проблем при оценке производительности ConcurrentSkipListMap заключается в том, что операции обхода «убирают» маркеры, оставленные предыдущими удалениями.Таким образом, сложность операции может фактически зависеть от того, какими были предыдущие операции.(С другой стороны, на каком-то уровне это справедливо практически для любого алгоритма:находятся ли некоторые данные в кеше ЦП, может зависеть от того, поместила ли их туда предыдущая операция...)

P.S.Забыл сказать:посмотри на ConcurrentSkipListMap.pollFirstEntry().

Answer 4

std:multimap будет древовидной структурой, а это означает, что сложение и удаление вместе составит O (log n).