home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / b_priori.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.3 KB  |  49 lines
  1.  
  2. {\magonebf 4.2 Bounded Priority Queues (b\_priority\_queue)}
  3.  
  4. An instance $Q$ of the data type $b\_priority\_queue$ is a priority\_queue
  5. (cf. section 4.1) whose items contain informations from a fixed interval 
  6. $[a..b]$ of integers.
  7.  
  8. \bigskip
  9. {\bf 1. Declaration of a bounded priority queue type }
  10.  
  11.  
  12. \decl b\_priority\_queue K 
  13.  
  14. introduces a new data type with name \name\ consisting of all
  15. bounded priority queues with key type $K$.
  16.  
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation of a bounded priority queue}
  21.  
  22. \create Q {(a,b)}
  23.  
  24. creates an instance \var\ of type \name\ with information type $[a..b]$
  25. and initializes it with the empty priority queue.
  26.  
  27.  
  28.  
  29. \bigskip
  30. {\bf 3. \operations }
  31.  
  32. The operations are the same as for the data type $priority\_queue$ with
  33. the additional precondition that any information argument must be
  34. in the range $[a..b]$.
  35.  
  36.  
  37. \bigskip
  38. {\bf 4. Implementation}
  39.  
  40. Bounded priority queues are implemented by arrays of linear lists.
  41. Operations insert, find\_min, del\_item, decrease\_inf, key, inf, 
  42. and empty take time $O(1)$, del\_min ( =  del\_item for the minimal
  43. element) takes time $O(d)$, where $d$ is the distance of the minimal
  44. element to the next bigger element in the queue ( = $O(b-a)$ in the
  45. worst case). clear takes time $O(b-a+n)$ and the space requirement is 
  46. $O(b-a+n)$, where $n$ is the current size of the queue.
  47.  
  48.  
  49.