Bounded Node Priority Queues (b_node_pq)

Definition

An instance of the data type b_node_pq<N> is a priority queue of nodes with integer priorities with the restriction that the size of the minimal interval containing all priorities in the queue is bounded by N, the minimum priority is never decreasing, and every node is contained in at most one queue. When applied to the empty queue the del_min - operation returns a special default minimum node defined in the constructor of the queue.

Creation

b_node_pq<N>	PQ;	introduces a variable PQ of type b_node_pq<N> and initializes it with the empty queue with default minimum node nil.
b_node_pq<N>	PQ(node v);	introduces a variable PQ of type b_node_pq<N> and initializes it with the empty queue with default minimum node v.

Operations

node	PQ.del_min()	removes the node with minimal priority from PQ and returns it (the default minimum node if PQ is empty).
void	PQ.insert(node w, int p)	adds node w with priority p to PQ.
void	PQ.del(node w)	deletes node w from PQ.

Implementation

Bounded node priority queues are implemented by cyclic arrays of doubly linked node lists.

Example

Using a b_node_pq in Dijktra's shortest paths algorithm.

int dijkstra(const GRAPH<int,int>& g, node s, node t) 
{ node_array<int> dist(g,MAXINT);
  b_node_pq<100> PQ(t);  // on empty queue del_min returns t 
  dist[s] = 0;

  for (node v = s;  v != t; v = PQ.del_min() )
  { int dv = dist[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g.inf(e);
      if (d < dist[w])
      { if (dist[w] != MAXINT) PQ.del(w);
        dist[w] = d;
        PQ.insert(w,d);
       }
     }
   }
  return dist[t];
}