Definition
An instance Q of the parameterized data type node_pq<P> is a partial function from the nodes of a graph G to a linearly ordered type P of priorities. The priority of a node is sometimes called the information of the node. For every graph G only one node_pq<P> may be used and every node of G may be contained in the queue at most once (cf. section Priority Queues for general priority queues).
#include < LEDA/graph/node_pq.h >
Creation
node_pq<P> | Q(const graph_t& G) | creates an instance Q of type node_pq<P> for the nodes of graph G with dom(Q) = . |
Operations
Implementation
Node priority queues are implemented by binary heaps and node arrays. Operations insert, del_node, del_min, decrease_p take time O(log m), find_min and empty take time O(1) and clear takes time O(m), where m is the size of Q. The space requirement is O(n), where n is the number of nodes of G.