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

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

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

4 2
c++ data-structures multimap priority-queue

4 ответа:

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

2

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

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

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

2

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

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

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

1

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

0