\manpage {node\_pq} {P} {Node Priority Queues}
 
\definition
An instance $Q$ of the parameterized data type \name\ 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.
 
\creation Q 
 
\create {(graph\ G)}
   { creates an instance $Q$ ot type \name\ for the nodes of graph $G$
    with $dom(Q)=\emptyset$. }
 
 
\operations 1.3 4.7
 
\op  void insert {(node\ v, \ P\ x)}
           {  adds the node $v$ with priority $x$ to
          	 \var.\\ \precond $v\not\in dom(Q)$. }
 
 
\op  P prio {(node\ v)}
           {  returns the priority of node $v$. }
 
 
\op  bool member {(node\ v)}
           {  returns true if $v$ in \var, false otherwise. }
 
 
\op  void decrease\_p {(node\ v, \ P\ x)}
           {  makes $x$ the new priority of node $v$.\\
        	 \precond $p \le Q$.prio$(v)$. }
 
 
\op  node find\_min {()}
           {  returns a node with minimal priority
                 (nil if \var\ is empty). }
 
 
\op  void del {(node\ v)}
           {  removes the node $v$ from \var.  }
 
 
\op  node del\_min {()}
           {  removes a node with minimal priority from \var\
                 and returns it (nil if \var\ is empty). }
 
 
\op  void clear {()}
           {  makes $Q$ the empty node priority queue. }
 
 
\op  int size {()}
           {  returns $|dom(Q)|$.  }
 
 
\op  int empty {()}
           {  returns true if \var\ is the empty node
		 priority queue, false otherwise. }
 
 
\op  P inf {(node\ v)}
           {  returns the priority of node $v$. }
 
 
\implementation
Node priority queues are implemented by fibonacci heaps and node arrays.
Operations insert, del\_node, del\_min take time $O(\log n)$, find\_min, 
decrease\_inf, 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$.
 
