home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / priority.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  3.1 KB  |  97 lines
  1. {\magonebf 4.1 Priority Queues (priority\_queue)}
  2.  
  3. An instance $Q$ of the data type $priority\_queue$ is a collection of items 
  4. (type $pq\_item$). Every item contains a key from a type K and an information 
  5. from a linearly ordered type $I$. $K$ is called the key type of $Q$ and $I$ is 
  6. called the information type of $Q$. The number of items in $Q$ is called the 
  7. size of $Q$. If $Q$ has size zero it is called the empty priority queue. We 
  8. use $<k,i>$ to denote a $pq\_item$\ with key $k$ and information $i$. 
  9. on $I$.
  10.  
  11.  
  12.  
  13. \bigskip
  14. {\bf 1. Declaration of a priority queue type }
  15.  
  16.  
  17. \decltwo priority\_queue K I 
  18.  
  19. introduces a new data type with name \name\ consisting of all
  20. priority queues with key type $K$ and information type $I$.
  21. \precond $I$ is linearly ordered.
  22.  
  23.  
  24.  
  25. \bigskip
  26. {\bf 2. Creation of a priority queue}
  27.  
  28.  
  29. \create Q {}
  30.  
  31. creates an instance \var\ of type \name\ and initializes it with the
  32. empty priority queue.
  33.  
  34.  
  35.  
  36. \bigskip
  37. {\bf 3. \operations }
  38.  
  39. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  40. \+\op K        key {pq\_item\ it}    
  41.                            {returns the key of item $it$.}
  42. \+\nop                     {\precond $it$ is an item in \var.}
  43. \smallskip
  44. \+\op I        inf {pq\_item\ it}    
  45.                            {returns the information of item $it$.}
  46. \+\nop                     {\precond $it$ is an item in \var.}
  47. \smallskip
  48. \+\op pq\_item insert {K\ k,I\ i} 
  49.                            {adds a new item $<k,i>$ to \var\ and returns $it$.}
  50. \smallskip
  51. \+\op pq\_item find\_min {}       
  52.                            {returns an item with minimal information}
  53. \+\nop                     {(nil if \var\ is empty)}
  54. \smallskip
  55. \+\op void     del\_item {pq\_item\ it} 
  56.                            {removes the item $it$ from \var.}
  57. \+\nop                     {\precond $it$ is an item in \var.}
  58. \smallskip
  59. \+\op K        del\_min {} 
  60.                            {removes the item with minimal information}
  61. \+\nop                     {from \var\ and returns its key.}
  62. \+\nop                     {\precond \var\ is not empty.}
  63. \smallskip
  64. \+\op pq\_item decrease\_inf {pq\_item\ it,\ I\ i} 
  65.                            {makes i the new information of item $it$}
  66. \+\nop                     {\precond $it$ is an item in \var\ and $i$}
  67. \+\nop                     {is not larger then $inf(it)$.}
  68. \smallskip
  69. \+\op void     change\_key {pq\_item\ it,\ K\ k} 
  70.                            {makes k the new key of item $it$}
  71. \+\nop                     {\precond $it$ is an item in \var.}
  72. \smallskip
  73. \+\op void     clear {}        
  74.                            {makes \var\ the empty priority queue }
  75. \smallskip
  76. \+\op bool     empty {} 
  77.                            {returns true, if \var\ is empty, false otherwise}
  78. \smallskip
  79. \+\op int      size  {}
  80.                            {returns the size of \var.}
  81.  
  82.  
  83. \bigskip
  84. {\bf 4. Implementation}
  85.  
  86. Priority queues are implemented by Fibonacci heaps ([FT84]. Operations insert, 
  87. del\_item, del\_min take time $O(\log n)$, find\_min, decrease\_inf, 
  88. key, inf, empty take time $O(1)$ and clear takes time $O(n)$, where $n$ is the 
  89. size of \var. The space requirement is $O(n)$.
  90.  
  91.  
  92. \bigskip
  93. {\bf 5. Example}
  94.  
  95. Dijkstra's Algorithm (cf. section 8.1)
  96.  
  97.