Приоритетная очередь с изменением значений ключа

Question

Мне нужно смоделировать очередь с приоритетами. Ключи в очереди периодически меняются. Очередь должна быть в состоянии: добавить элемент и удалить элемент. Каков наилучший способ сделать это (с лучшей сложностью)? Какая структура данных лучше?

Answer 1

Я бы рекомендовал один из двух подходов:

1. (Дополнительно) Используйте структуру данных кучи, используемую реализацией Java PriorityQueue. При изменении приоритета элемента вам нужно будет выполнить операции «sift up» и «sift down» в куче, чтобы убедиться, что вершина кучи по-прежнему представляет самый высокий элемент в очереди с приоритетами. Sift-up и sift-down - это операции, которые составляют часть heapsort .
2. (Простой). Используйте неупорядоченный список в качестве приоритетной очереди. Это означает, что элементы могут быть вставлены с временем доступа O (1), и настройка приоритета элемента не требует каких-либо манипуляций со структурой данных. Однако компромисс заключается в том, что для доступа к элементу с наивысшим приоритетом используется O (n).

Answer 2

Всегда трудно сказать, что такое «лучшая» структура данных. В общем случае двоичная куча создает очередь с очень хорошим приоритетом, хотя изменить приоритет элемента сложно. В прошлом я занимался созданием структуры данных, которая объединяет словарь и кучу. Словарь определяется по идентификатору элемента и отслеживает местоположение каждого элемента в куче. Когда элемент добавляется, удаляется или перемещается в куче, его местоположение обновляется в словаре. Это оказывается недорого.

Теперь, когда вы хотите изменить приоритет элемента или удалить произвольный элемент из очереди приоритетов, вы можете найти его в словаре (O(1)), чтобы получить его позицию в куче. Оттуда это O(log n) операция по перемещению или удалению.

Вы также можете использовать сбалансированное двоичное дерево для своей очереди приоритетов. Достаточно просто сохранить указатель «самого низкого узла», и операции над деревом являются O(log n). Если вставки и удаления довольно хорошо рассеяны, это должно работать достаточно хорошо. Недостаток в том, что код для реализации самобалансирующегося двоичного дерева немного сложен.

Другой возможностью является использование списка пропуска для вашей приоритетной очереди. Мои тесты показывают, что очередь приоритетов с пропущенным списком выгодно отличается от очереди приоритетов на основе двоичной кучи, но имеет одно большое преимущество: поиск элемента O(log n) вместо O(n). И список пропусков не намного сложнее реализовать, чем двоичная куча.

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

Answer 3

Если вы ищете структуру данных, которая может поддерживать постоянные изменения в произвольных ключах, а также удаление / добавление произвольных ключей [произвольный == не заголовок в этом ответе], обычная куча не сработает, поскольку он не гарантирует быстрый поиск произвольных элементов, только по голове.

Вы можете использовать полностью упорядоченную структуру, такую ​​как сбалансированный BST , и кэшировать мин / макс при каждом изменении дерева. [min - самый левый элемент, max - самый правый элемент].

Это позволит вам:
удалить, изменить, добавить: O(logn)
findMin / findMax: O(1)

Answer 4

Если вы просто храните числа в качестве ключей, класс ArrayList должен работать нормально.

queue = new ArrayList<int>;
queue.add(27);