
{\magonebf 4.2 Bounded Priority Queues (b\_priority\_queue)}

An instance $Q$ of the data type $b\_priority\_queue$ is a priority\_queue
(cf. section 4.1) whose items contain informations from a fixed interval 
$[a..b]$ of integers.

\bigskip
{\bf 1. Declaration of a bounded priority queue type }


\decl b\_priority\_queue K 

introduces a new data type with name \name\ consisting of all
bounded priority queues with key type $K$.



\bigskip
{\bf 2. Creation of a bounded priority queue}

\create Q {(a,b)}

creates an instance \var\ of type \name\ with information type $[a..b]$
and initializes it with the empty priority queue.



\bigskip
{\bf 3. \operations }

The operations are the same as for the data type $priority\_queue$ with
the additional precondition that any information argument must be
in the range $[a..b]$.


\bigskip
{\bf 4. 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.


