How to update element priorities in a heap for Prim's Algorithm?

Question

I am studying Prim's Algorithm. There is a part within the code the next vertex across the cut will be coming to the set of the vertices belonging to the MST. While doing that, we also have to 'update all vertices in the other set which are adjacent to the departing vertex'. This is a snapshot from CLRS:

The interesting part lies in line no. 11. But since we are using a heap here, we have access to only the minimum element, right (heap[0])? So how do we search and update vertices from the heap even though they are not the minimum one and thus we have knowing where they are except by linear search?

Answer 1

It is possible to build priority queues that support an operation called decrease-key, which takes the priority of an existing object in a priority queue and lowers it. Most versions of priority queues that ship with existing libraries don't support this operation, but it's possible to build it in several ways.

For example, given a binary heap, you can maintain an auxiliary data structure that maps from elements to their positions in the binary heap. You would then update the binary heap implementation so that whenever a swap is performed, this auxiliary data structure is updated. Then, to implement decrease-key, you could access the table, find the position of the node in the binary heap, then continue a bubble-up step.

Other pointer-based heaps like binomial heaps or Fibonacci heaps explicitly support this operation (the Fibonacci heap was specifically designed for it). You usually have an auxiliary map from objects to the node they occupy in the heap and can then rewire the pointers to move the node around in the heap.

Hope this helps!

Answer 2

Pointers enable efficient composite data structures

You have something like this (using pseudocode C++):

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

The priority queue Q in the algorithm contains items of type Node*, where ExtractMin gets you the Node* with minimum key.

The reason you don't have to do any linear search is because, when you get u = ExtractMin(Q), you have a Node*. So u->adjacent gets you both the v's in G.Adj[u] and the w(u,v)'s in const time per adjacent node. Since you have a pointer v to the priority queue node (which is v), you can update it's position in the priority queue in logarithmic time per adjacent node (with most implementations of a priority queue).

To name some specific data structures, the DecreaseKey(Q, v) function used below has logarithmic complexity for Fibonnaci heaps and pairing heaps (amortized).

• Pairing heap: http://en.wikipedia.org/wiki/Pairing_heap
  • Not too hard to code yourself - Wikipedia has most of the source code
• Fibonacci heap: http://en.wikipedia.org/wiki/Fibonacci_heap

More-concrete pseudocode for the algorithm

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)