Как обновить приоритеты элементов в куче для алгоритма Prim?

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

enter image description here

Интересная часть лежит в строке №. 11. Но поскольку мы используем кучу здесь, у нас есть доступ только к минимальному элементу, справа (heap[0])? Итак, как мы можем искать и обновлять вершины из кучи, даже если они не являются минимальными, и поэтому мы знаем, где они находятся, кроме линейного поиска?

Ответы

Ответ 1

Можно создать очереди приоритетов, поддерживающие операцию с именем reduce-key, которая принимает приоритет существующего объекта в очереди приоритетов и снижает его. Большинство версий очередей приоритетов, которые поставляются с существующими библиотеками, не поддерживают эту операцию, но ее можно построить несколькими способами.

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

Другие кучи на основе указателей, такие как биномиальные кучи или кучи Фибоначчи, явно поддерживают эту операцию (куча Фибоначчи была специально разработана для нее). Обычно у вас есть вспомогательная карта из объектов в node, которые они занимают в куче, и затем может перерисовывать указатели, чтобы перемещать node в кучу.

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

Ответ 2

Указатели позволяют создавать эффективные составные структуры данных

У вас есть что-то вроде этого (с использованием псевдокода С++):

class Node
    bool visited
    double key
    Node* pi
    vector<pair<Node*, double>> adjacent //adjacent nodes and edge weights
    //and extra fields needed for PriorityQueue data structure
    // - a clean way to do this is to use CRTP for defining the base
    //   PriorityQueue node class, then inherit your graph node from that

class Graph
    vector<Node*> vertices

CRTP: http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern

Очередь приоритетов Q в алгоритме содержит элементы типа Node*, где ExtractMin получает Node* с минимальным значением key.

Причиной вам не нужно делать линейный поиск, потому что, когда вы получаете u = ExtractMin(Q), у вас есть Node*. Итак, u->adjacent получает вас как v в G.Adj[u], так и w(u,v) в const время на смежный node. Поскольку у вас есть указатель v в очереди приоритетов node (который есть v), вы можете обновить его положение в очереди приоритетов в логарифмическом времени на смежном node (с большинством реализации очереди приоритетов).

Чтобы назвать некоторые конкретные структуры данных, функция DecreaseKey(Q, v), используемая ниже, имеет логарифмическую сложность для кучи Fibonnaci и спаривания кучи (амортизируется).

Больше-бетонный псевдокод для алгоритма

MstPrim(Graph* G)
    for each u in G->vertices
        u->visited = false
        u->key = infinity
        u->pi = NULL
    Q = PriorityQueue(G->vertices)
    while Q not empty
        u = ExtractMin(Q)
        u->visited = true
        for each (v, w) in u->adjacent
            if not v->visited and w < v->key
                v->pi = u
                v->key = w
                DecreasedKey(Q, v) //O(log n)