Используемая структура данных: необходимо получить доступ как по приоритету, так и по имени

Какую структуру данных использовать, когда мне нужно

  • получить доступ к объекту по приоритету - исключить из очереди
  • получить доступ к объекту по имени/идентификатору, чтобы обновить приоритет

С Java PriorityQueue я не могу получить доступ к узлу напрямую по его имени/идентификатору, не так ли?

Я думал об использовании приоритетной очереди плюс TreeMap, чтобы я мог искать по имени в журнале (n) времени, а затем изменять приоритет. Но я сомневаюсь, что Очередь узнает об этом? В этом случае мне нужно удалить и снова добавить узел? Стоит ли это накладных расходов? Какая сложность удаления/повторного добавления узла?


java priority-queue
person Jiew Meng    schedule 12.09.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В этом случае мне нужно удалить и снова добавить узел?

да.

Стоит ли это накладных расходов?

Это зависит от ваших требований. Только ты это знаешь.

Какая сложность удаления/повторного добавления узла?

Вставка и удаление из PriorityQueue — это O(log n).

person Peter Lawrey    schedule 12.09.2012
comment
Итак, по вашему мнению, это наиболее подходящая структура данных для этого варианта использования? Или есть что-то лучше? - person Jiew Meng; 12.09.2012
comment
Если вам нужно изменить приоритет на основе отсортированного ключа, это лучшая комбинация, которую я могу придумать. Если вы можете использовать HashMap вместо TreeMap, это будет немного быстрее, чем его O (1), но PriorityQueue все равно будет O (log n). - person Peter Lawrey; 12.09.2012
comment
Я предполагаю, что решение выбрать Tree или Hash Map будет вероятностью столкновения для набора данных? Как узнать, мала или велика вероятность столкновения набора данных? - person Jiew Meng; 12.09.2012
comment
Я бы предположил, что он маленький, если у вас плохой хэш-код. Если hashCode всегда равен 1, не используйте HashMap. ;) - person Peter Lawrey; 12.09.2012
comment
Я буду использовать все, что делает java в этом случае. Но я полагаю, ты имеешь в виду, что если у моего имени может быть много дубликатов, то это плохая идея? Если это так, я думаю, что набор хэшей - это путь, поскольку в этом случае имена должны быть уникальными. - person Jiew Meng; 12.09.2012
comment
Карта не может иметь повторяющихся ключей, поэтому у вас возникнут проблемы независимо от того, какую карту вы используете. Проблема в том, что многие ключи имеют одинаковый хэш-код. Я бы использовал карту, а не набор. - person Peter Lawrey; 12.09.2012