Node Priority Queues
The data type node_pq<P> can be used to store nodes of a
Graphs together with an associated priority
of a linearly
ordered type P. Node Priority Queues are specialized versions
of Priority Queues.
In a Node Priority Queue the node with the minimum priority can be
accessed very efficiently.
Example of how to use
a node priority queue
Strengths
 functions
find_min(), empty() only need constant time
insert(), del_node(), del_min(), decrease_p() only need time
O(log m) where m is the size of the queue
Disadvantages
 only one node priority queue can be used for every graph.
 every node may be contained in the queue at most once.
 space requirement is O(n), where n is the number of nodes of the
graph.
Tips
 Prefer node_pq to
p_queue<node> whereever possible.

See also:
Priority Queues
Bounded Node Priority Queue
Manual Entries:
Manual Page Node Priority Queues
Linear
Orders
