home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / node_pq.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.0 KB  |  76 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.11 Node priority queues (node\_pq)}
  4.  
  5.  
  6. An instance $Q$ of the data type $node\_pq$ is a partial function from the nodes
  7. of a graph $G$ to some linearly ordered type $I$.
  8.  
  9.  
  10. \bigskip
  11. {\bf 1. Declaration of a node priority queue type}
  12.  
  13.  
  14. \decl node\_pq I 
  15.  
  16. introduces a new data type with name \name\ consisting of all node 
  17. priority queues with information type $I$.
  18.  
  19.  
  20.  
  21. \bigskip
  22. {\bf 2. Creating a node priority queue}
  23.  
  24.  
  25. \create Q (G)
  26.  
  27. creates an instance $Q$ ot type \name\ for the nodes of graph $G$
  28. with $dom(Q)=\emptyset$.
  29.  
  30.  
  31.  
  32. \bigskip
  33. {\bf 3. \operations} 
  34.  
  35. \medskip
  36. \+\op void insert {node\ v,\ I\ i}    
  37.                         {adds the node $v$ with information $i$ to}
  38. \+\nop                  {\var. \precond $v\not\in dom(Q)$.}
  39. \smallskip
  40. \+\op void decrease\_inf {node\ v,\ I\ i} 
  41.                         {makes $i$ the new information of node $v$}
  42. \+\nop                  {(\precond $i \leq Q(v)$)}
  43. \smallskip
  44. \+\op node find\_min {}          
  45.                         {returns a node with the minimal }
  46. \+\nop                  {information(nil if \var\ is empty)}
  47. \smallskip
  48. \+\op void del {node\ v}           
  49.                         {removes the node $v$ from \var }
  50. \smallskip
  51. \+\op node del\_min {}             
  52.                         {removes a node with the minimal}
  53. \+\nop                  {information from \var\ and returns it}
  54. \+\nop                  {(nil if \var\ is empty)}
  55. \smallskip
  56. \+\op void clear {}                 
  57.                         {makes $Q$ the empty node priority queue.}
  58. \smallskip
  59.  
  60. \+\op bool  empty {}                 
  61.                         {returns true if \var\ is the empty node}
  62. \+\nop                  {priority queue, false otherwise.}
  63.  
  64.  
  65. \bigskip
  66. {\bf 4. Implementation}
  67.  
  68. Node priority queues are implemented by fibonacci heaps and node arrays.
  69. Operations insert, del\_node, del\_min take time $O(\log n)$, find\_min, 
  70. decrease\_inf, empty take time $O(1)$ and clear takes time $O(m)$, where 
  71. $m$ is the size of $Q$. The space requirement is $O(n)$, where $n$ is the 
  72. number of nodes of $G$.
  73.  
  74. \vfill\eject
  75.  
  76.