Самый простой способ использования очереди с минимальным приоритетом с обновлением ключа в С++

Иногда во время конкурсов программирования и т.д. нам нужна простая рабочая реализация очереди с минимальным приоритетом с помощью клавиши уменьшения для реализации алгоритма Дейкстры и т.д. Я часто использую set < пара < key_value, идентификатор → и массив (идентификатор сопоставления → key_value) вместе для достижения этого.

Добавление элемента в набор занимает время O (log (N)). Чтобы построить приоритетную очередь из N элементов, мы просто добавляем их по одному в набор. Это занимает общее время O (N log (N)).
Элемент с min key_value - это просто первый элемент набора. Пробывание наименьшего элемента занимает O (1) раз. Для удаления требуется время O (log (N)).
Чтобы проверить, установлен ли какой-либо ID = k в наборе, сначала рассмотрим его key_value = v_k в массиве, а затем выполните поиск элемента (v_k, k) в наборе. Это занимает время O (log (N)).
Чтобы изменить значение key_value некоторого ID = k из v_k в v_k ', сначала рассмотрим его key_value = v_k в массиве, а затем выполните поиск элемента (v_k, k) в наборе. Затем мы удалим этот элемент из набора, а затем вставим элемент (v_k ', k) в набор. Затем мы также обновляем массив. Это занимает время O (log (N)).

Хотя вышеупомянутый подход работает, большинство учебников обычно рекомендуют использовать двоичные кучи для реализации очередей приоритетов, так как время построения двоичных куч - это просто O (N). Я слышал, что в STL С++ есть встроенная структура данных очереди приоритетов, которая использует двоичные кучи. Однако я не уверен, как обновить значение key_value для этой структуры данных.

Какой самый простой и эффективный способ использования очереди минимального приоритета с обновлением ключа в С++?

Ответ 1

Ну, как сказал Даррен, std::priority_queue не имеет средств для уменьшения приоритета элемента, и ни удаление элемент, отличный от текущего мин. Но по умолчанию std::priority_queue представляет собой не что иное, как простой контейнерный адаптер вокруг std::vector, который использует функции кучи std из <algorithm> (std::push_heap, std::pop_heap и std::make_heap). Поэтому для Dijkstra (где вам требуется обновление приоритета) я обычно делаю это сам и использую простой std::vector.

Нажатие - это просто операция O (log N)

vec.push_back(item);
std::push_heap(vec.begin(), vec.end());

Конечно, для построения очереди заново из N элементов мы не нажимаем их все, используя эту операцию O (log N) (делая всю вещь O (Nlog N)), но просто помещаем их все в вектор, за которым следует простой O (N)

std::make_heap(vec.begin(), vec.end());

Элемент min является простым O (1)

vec.front();

Поп - это простая последовательность O (log N)

std::pop_heap(vec.begin(), vec.end());
vec.pop_back();

До сих пор это именно то, что std::priority_queue обычно делает под капотом. Теперь, чтобы изменить приоритет элемента, нам просто нужно его изменить (однако он может быть включен в тип элемента) и сделать последовательность действительной кучей снова

std::make_heap(vec.begin(), vec.end());

Я знаю, что это операция O (N), но, с другой стороны, это устраняет необходимость отслеживать позицию позиции в куче с дополнительной структурой данных или (что еще хуже) увеличение типа элементов, Снижение производительности по сравнению с логарифмическим приоритетным обновлением на практике не так важно, учитывая простоту использования, использование компактной и линейной памяти std::vector (что также влияет на время выполнения), а также тот факт, что я часто работаю с графиками, которые имеют впрочем, несколько ребер (линейных по количеству вершин).

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

EDIT: О, и поскольку стандартная библиотека использует max-heaps, вам нужно использовать эквивалент > для сравнения приоритетов (однако вы получаете их из элементов), а не по умолчанию <.

Ответ 2

Я не думаю, что класс std::priority_queue позволяет эффективно выполнять операции стиля decrease-key.

Я развернул свою собственную структуру данных на основе двоичной кучи, которая поддерживает это, в основном по очень сходным строкам с тем, что вы описали для очереди приоритетов на основе std::set:

Поддерживает двоичную кучу, отсортированную по value, которая хранит элементы pair<value, ID> и массив, который отображает ID -> heap_index. Внутри подпрограмм кучи heapify_up, heapify_down и т.д. Необходимо убедиться, что массив отображения поддерживается синхронно с текущей ячейкой кучи элементов. Это добавляет дополнительные дополнительные O(1) служебные данные.
Преобразование массива в кучу можно сделать в O(N) в соответствии со стандартным алгоритмом, описанным здесь.
Peeking у корневого элемента O(1).
Проверка наличия в куче ID требует только поиска O(1) в массиве сопоставления. Это также позволяет O(1) заглянуть в элемент, соответствующий любому ID.
decrease-key требует поиска O(1) в массиве отображения, за которым следует обновление O(log(N)) в кучу через heapify_up, heapify_down.
Нажатие нового элемента в кучу O(log(N)), когда выталкивает элемент удаления из кучи.

Таким образом, асимптотически время выполнения улучшено для нескольких операций по сравнению с структурой данных на основе std::set. Другим важным улучшением является то, что двоичные кучи могут быть реализованы в массиве, а бинарные деревья - контейнеры на основе node. Дополнительная локальность данных двоичной кучи обычно переводится в улучшенное время выполнения.

Несколько проблем с этой реализацией:

Он допускает только целочисленный элемент ID.
Он предполагает плотное распределение элемента ID, начиная с нуля (в противном случае сложность пространства массива отображения взрывается!).

Вы можете потенциально преодолеть эти проблемы, если вы сохранили хэш-таблицу сопоставления, а не массив сопоставления, но с небольшими дополнительными издержками времени исполнения. Для моего использования целых ID всегда было достаточно.

Надеюсь, что это поможет.

Ответ 3

Хотя мой ответ не отвечает на исходный вопрос, я думаю, что это может быть полезно для людей, которые достигают этого вопроса при попытке реализовать алгоритм Дейкстры в С++/Java (например, я), что-то, что было комментарием OP,

priority_queue в С++ (или PriorityQueue в Java) не предоставляют операцию decrease-key, как было сказано ранее. Хороший трюк для использования этих классов при реализации Dijkstra использует "ленивое удаление". Основной цикл алгоритма Дейкстры извлекает следующий node для обработки из очереди приоритетов и анализирует все его соседние узлы, в конечном счете изменяя стоимость минимального пути для node в очереди приоритетов. Это то место, где decrease-key обычно требуется для обновления значения этого node.

Трюк не изменит его вообще. Вместо этого в очередь приоритетов добавляется "новая копия" для этого node (с его новой лучшей стоимостью). Имея более низкую стоимость, новая копия node будет извлечена перед исходной копией в очереди, поэтому она будет обработана раньше.

Проблема с этим "ленивым удалением" заключается в том, что вторая копия node с более высокой плохими затратами будет в конечном итоге извлечена из очереди приоритетов. Но это всегда будет происходить после обработки второй добавленной копии с лучшей стоимостью. Итак, самое первое, что должен сделать основной цикл Dijkstra при извлечении следующего node из очереди приоритетов, - это проверка того, что ранее был посещен node (и мы знаем самый короткий путь уже). Именно в тот точный момент, когда мы будем делать "ленивое удаление", и элемент должен просто игнорироваться.

Это решение будет стоить как в памяти, так и в времени, потому что приоритетная очередь хранит "мертвые элементы", которые мы не удалили. Но реальная стоимость будет довольно небольшой, и программирование этого решения, ИМХО, проще, чем любая другая альтернатива, которая пытается имитировать отсутствующую операцию decrease-key.