\manpage {p\_queue} {P,I} {Priority Queues}
 
\definition
An instance $Q$ of the parameterized data type \name\ is a collection of items
(type $pq\_item$). Every item contains a priority from a linearly ordered type 
$P$ and an information from an arbitrary type $I$. $P$ is called the priority 
type of $Q$ and $I$ is called the information type of $Q$. The number of items 
in $Q$ is called the size of $Q$. If $Q$ has size zero it is called the empty 
priority queue. We use $\<p,i\>$ to denote a $pq\_item$\ with priority $p$ and
information $i$.
 
\creation Q 
 
\create { }
   {
creates an instance \var\ of type \name\ and initializes it with the
empty priority queue.  }
 
 
\operations 2 5
 
\op  P prio {(pq\_item\ it)}
           {  returns the priority of item $it$.\\
            \precond $it$ is an item in \var. }
 
 
\op  I inf {(pq\_item\ it)}
           {  returns the information of item $it$.\\
	    \precond $it$ is an item in \var. }
 
 
\op  pq\_item insert {(P\ x, \ I\ i)}
           {  adds a new item $\<x,i\>$ to \var\ and returns it. }
 
 
\op  pq\_item find\_min {()}
           {  returns an item with minimal information
	    (nil if \var\ is empty). }
 
 
\op  P   del\_min {()}
           {  removes the item $it$ = \var.find\_min() from \var\
	   and returns the priority of it.\\
           \precond \var\ is not empty. }
 
 
\op  void del\_item {(pq\_item\ it)}
           {  removes the item $it$ from \var.\\
	   \precond $it$ is an item in \var. }
 
 
\op  void change\_inf {(pq\_item\ it, \ I\ i)}
           {  makes $i$ the new information of item $it$.\\
	   \precond $it$ is an item in \var. }
 
 
\opl void decrease\_p {(pq\_item\ it, \ P\ x)}
           {  makes $x$ the new priority of item $it$.\\
	    \precond $it$ is an item in \var\ and $x$
	    is not larger then $prio(it)$. }
 
 
\op  int  size {()}
           {  returns the size of \var. }
 
 
\op  bool empty {()}
           {  returns true, if \var\ is empty, false otherwise. }
 
 
\op  void clear {()}
           {  makes \var\ the empty priority queue.  }
 
 
\implementation
Priority queues are implemented by Fibonacci heaps \cite{FT87}. Operations
insert, del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_p, 
prio, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
size of \var. The space requirement is $O(n)$.
 
\example
Dijkstra's Algorithm (cf. section \ref{Graph and network algorithms})
 
