Node Priority Queues (node_pq)

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).

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.