Когда я должен использовать TreeMap поверх PriorityQueue и наоборот?

Question

Кажется, они оба позволяют вам получить минимум, который мне нужен для алгоритма Прима, и вынуждают меня удалить и заново вставить ключ, чтобы обновить его значение. Есть ли преимущество использования одного над другим, не только для этого примера, но и вообще?

Answer 1

Вообще говоря, отслеживание только минимального элемента с использованием кучи занимает меньше времени.

Дерево более организовано, и для его поддержки требуется больше вычислений. Но если вам нужен доступ к любому ключу, а не только к минимуму, кучи не хватит, и дополнительные издержки дерева оправданы.

Answer 2

Полностью согласен с Эриксоном в том, что приоритетная очередь дает вам только минимальный / максимальный элемент.

Кроме того, поскольку очередь приоритетов менее мощна для поддержания общего порядка данных, она имеет преимущество в некоторых особых случаях. Если вы хотите отслеживать самые большие M элементы в массиве N, временная сложность будет O(N*LogM), а сложность пространства будет O(M). Но если вы делаете это на карте, временная сложность составляет O(N*logN), а пространство - O(N). Это довольно фундаментально, в то время как в некоторых случаях мы должны использовать приоритетную очередь, например M - это просто константа, такая как 10.

Answer 3

Есть 2 различия, на которые я хотел бы указать (и это может быть более актуально для Разница между PriorityQueue и TreeSet в Java? , поскольку этот вопрос считается дубликатом этого вопроса).

(1) PriorityQueue может иметь дубликаты, тогда как TreeSet НЕ может иметь дублирования.Поэтому в Treeset, если ваш компаратор считает 2 элемента равными, TreeSet сохранит только один из этих 2 элементов и отбросит другой.

(2) Итератор TreeSet обходит коллекцию в отсортированном порядке, тогда как PriorityQueueИтератор НЕ перемещается в отсортированном порядке.Для PriorityQueue Если вы хотите получить элементы в отсортированном порядке, вы должны уничтожить очередь путем многократного вызова remove ().

Я предполагаю, что обсуждение ограничено реализацией этих структур данных в Java.

Answer 4

Правило об этом:

TreeMap поддерживает все элементы в порядке.(Интуитивно понятно, что для его построения требуется время)

PriorityQueue гарантирует только мин или макс.Это дешевле, но менее мощно.

Answer 5

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

1. PriorityQueue позволяет дублировать (т. Е. С тем же приоритетом), а TreeMap - нет.
2. Сложность PriorityQueue равна O (n) (когда увеличивается, то его размер), а TreeMap равен O (logn) (так как он основан на Red Black Tree)
3. PriorityQueue основан на массиве, в то время как в TreeMap узлы связаны друг с другом,так, содержит метод PriorityQueue займет время O (n), а TreeMap займет время O (logn).

Answer 6

Одним из отличий является то, что remove (Object) и содержит (Object) линейные O (N) в PriorityQueue на основе обычной кучи (как в Oracle), но O (log (N)) для TreeSet / Map. 1001 *

Так что, если у вас есть большое количество элементов и вы делаете много удалений (Object) или содержит (Object), то TreeSet / Map может быть быстрее.

Answer 7

Это зависит от того, как вы реализуете свою очередь приоритетов. Согласно 2-й книге Кормена, самый быстрый результат - с кучей Фибоначчи