\manpage {b\_priority\_queue} {K} {Bounded Priority Queues}
 
\definition 
An instance $Q$ of the parameterized data type \name\ is a
priority\_queue (cf. section \ref{Priority Queues}) whose information type is a
fixed interval $[a..b]$ of integers.
 
\creation Q
 
\create {(int\ a,\ int\ b)}
   { creates an instance \var\ of type \name\ with information type
            $[a..b]$ and initializes it with the empty priority queue.  }
 
 
\operations 2 5.5 
 
 See section \ref{Priority Queues}.
 
\implementation
Bounded priority queues are implemented by arrays of linear lists.
Operations insert, find\_min, del\_item, decrease\_inf, key, inf,
and empty take time $O(1)$, del\_min ( =  del\_item for the minimal
element) takes time $O(d)$, where $d$ is the distance of the minimal
element to the next bigger element in the queue ( = $O(b-a)$ in the
worst case). clear takes time $O(b-a+n)$ and the space requirement is
$O(b-a+n)$, where $n$ is the current size of the queue.
 
