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

Question

Иногда во время соревнований по программированию и т. Д. Нам нужна простая рабочая реализация очереди с минимальным приоритетом с ключом уменьшения для реализации алгоритма Дейкстры и т. Д. Я часто использую set и массив (ID сопоставления -> 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 C ++ есть встроенная структура данных очереди приоритетов, которая использует двоичные кучи.Однако я не уверен, как обновить key_value для этой структуры данных.

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

Answer 1

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

Pop - это простая 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 (что также влияет на время выполнения), а также тот факт, что я часто работаю с графиками, которые имеют в любом случае, довольно мало ребер (линейных по числу вершин).

Это не во всех случаях может быть самый быстрый способ, но, безусловно, самый простой.

РЕДАКТИРОВАТЬ: О, и поскольку стандартная библиотека использует max-heaps, вам нужно использовать эквивалент > для сравнения приоритетов (однако вы получаете их из элементов), вместо значения по умолчанию < оператор.

Answer 2

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

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

Хитрость в том, что не изменить его .Вместо этого в новую очередь добавляется «новая копия» для этого узла (с его новой лучшей стоимостью).При более низкой стоимости новая копия узла будет извлечена перед исходной копией в очереди, поэтому она будет обработана раньше.

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

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

Answer 3

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

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

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

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

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

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

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

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