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/node _pq.h >
Creation
| node_pq<P> | Q(graph G) | creates an instance Q ot type node_pq<P> for the nodes of graph G with dom(Q) = emptyset . |
Operations
| void | Q.insert(node v, P x) | adds the node v with priority x to Q.
Precondition: v not in dom(Q). |
| P | Q.prio(node v) | returns the priority of node v. |
| bool | Q.member(node v) | returns true if v in Q, false otherwise. |
| void | Q.decrease_p(node v, P x) | makes x the new priority of node v.
Precondition: x < = Q.prio(v). |
| node | Q.find_min() | returns a node with minimal priority (nil if Q is empty). |
| void | Q.del(node v) | removes the node v from Q. |
| node | Q.del_min() | removes a node with minimal priority from Q and returns it (nil if Q is empty). |
| void | Q.clear() | makes Q the empty node priority queue. |
| int | Q.size() | returns | dom(Q)|. |
| int | Q.empty() | returns true if Q is the empty node priority queue, false otherwise. |
| P | Q.inf(node v) | returns the priority of node v. |
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.