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

Question

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

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

Answer 1

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

Answer 2

Попробуйте Apache Commons Collections.

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

Там тоже есть Priority Queue, но он амортизируется в пользу buffer package.

Answer 3

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

Answer 4

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

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

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