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

Question

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

Иногда во время соревнований по программированию и т. д. нам нужна простая рабочая реализация очереди с минимальным приоритетом с ключом уменьшения для реализации алгоритма Дейкстры и т. д. Я часто использую 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 ++?

53

c++ algorithm data-structures

задан xuhdev 19 March 2017 в 22:24

1 ответ

Другие вопросы по тегам:

c++ algorithm data-structures

Похожие вопросы:

score 0 · Answer 1

На самом деле существует способ использовать встроенную двоичную "кучу" из стандартной библиотеки C++. Ключевое наблюдение состоит в том что реализация всех функций "кучи" (т.е. станд.:: push_heap, станд.:: pop_heap и станд.:: make_heap), нуждаются только в следующих методах от сохраненного элемента класса A:

Конструктор A::A()
Оператор присваивания A& A::operator=(const A& rhs)
Оператор сравнения bool operator<(const A& lhs, const A& rhs)

Это означает, что оператор присваивания называют каждый раз, когда элемент перемещен в контейнер, хранящий все элементы "кучи". Путем перегрузки этого оператора можно управлять индексом в "куче". Когда у Вас есть индекс, можно получить доступ к элементу в "куче", изменить ее значение и вызов станд.:: pop_heap для обновления его положения в "куче".

Посмотрите упрощенное внедрение алгоритма Dijkstra (без графика):

#include <bits/stdc++.h>

using namespace std;

vector<int> queue_idx;

struct Elem {
    int label;
    int dist;
    bool operator<(const Elem& other) const { return dist > other.dist; }
    Elem& operator=(const Elem& other);
};

vector<Elem> q;

Elem& Elem::operator=(const Elem& other)
{
    label = other.label;
    dist = other.dist;
    queue_idx[label] = this - q.data();
    return *this;
}

void AddElem(int label, int dist)
{
    queue_idx[label] = label;
    q.push_back(Elem{label, dist});
}

void RemoveMin()
{
    pop_heap(q.begin(), q.end());
    Elem res = q.back();
    q.pop_back();
    cout << "dist to " << res.label << " is " << res.dist << endl;
}

void Relax(int label, int dist)
{
    int idx = queue_idx[label];
    Elem& elem = q[idx];
    if (elem.dist > dist)
    {
        elem.dist = dist;
        push_heap(q.begin(), q.begin() + idx + 1);
    }
}

int main()
{
    int n = 5;
    queue_idx.resize(n);
    AddElem(0, 0);
    for (int i = 1; i < n; ++i)
        AddElem(i, INT_MAX);
    make_heap(q.begin(), q.end());
    RemoveMin();
    Relax(1, 50);
    Relax(2, 40);
    Relax(4, 10);
    RemoveMin();
    Relax(3, 20);
    RemoveMin();
    Relax(1, 30);
    RemoveMin();
    Relax(2, 80);
    RemoveMin();
    return 0;
}

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