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:

Linear Orders