Java приоритет очереди

Question

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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