33 /// Fibonacci Heap. |
33 /// Fibonacci Heap. |
34 |
34 |
35 ///This class implements the \e Fibonacci \e heap data structure. A \e heap |
35 ///This class implements the \e Fibonacci \e heap data structure. A \e heap |
36 ///is a data structure for storing items with specified values called \e |
36 ///is a data structure for storing items with specified values called \e |
37 ///priorities in such a way that finding the item with minimum priority is |
37 ///priorities in such a way that finding the item with minimum priority is |
38 ///efficient. \ref Compare specifies the ordering of the priorities. In a heap |
38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
39 ///one can change the priority of an item, add or erase an item, etc. |
39 ///one can change the priority of an item, add or erase an item, etc. |
40 /// |
40 /// |
41 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
41 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
42 ///heap. In case of many calls to these operations, it is better to use a |
42 ///heap. In case of many calls to these operations, it is better to use a |
43 ///\e binary \e heap. |
43 ///\e binary \e heap. |
115 Adds \c item to the heap with priority \c value. |
115 Adds \c item to the heap with priority \c value. |
116 \pre \c item must not be stored in the heap. |
116 \pre \c item must not be stored in the heap. |
117 */ |
117 */ |
118 void push (Item const item, PrioType const value); |
118 void push (Item const item, PrioType const value); |
119 |
119 |
120 ///Returns the item with minimum priority relative to \ref Compare. |
120 ///Returns the item with minimum priority relative to \c Compare. |
121 |
121 |
122 /** |
122 /** |
123 This method returns the item with minimum priority relative to \ref |
123 This method returns the item with minimum priority relative to \c |
124 Compare. |
124 Compare. |
125 \pre The heap must be nonempty. |
125 \pre The heap must be nonempty. |
126 */ |
126 */ |
127 Item top() const { return container[minimum].name; } |
127 Item top() const { return container[minimum].name; } |
128 |
128 |
129 ///Returns the minimum priority relative to \ref Compare. |
129 ///Returns the minimum priority relative to \c Compare. |
130 |
130 |
131 /** |
131 /** |
132 It returns the minimum priority relative to \ref Compare. |
132 It returns the minimum priority relative to \c Compare. |
133 \pre The heap must be nonempty. |
133 \pre The heap must be nonempty. |
134 */ |
134 */ |
135 PrioType prio() const { return container[minimum].prio; } |
135 PrioType prio() const { return container[minimum].prio; } |
136 |
136 |
137 ///Returns the priority of \c item. |
137 ///Returns the priority of \c item. |
153 const PrioType& operator[](const Item& item) const { |
153 const PrioType& operator[](const Item& item) const { |
154 return container[iimap[item]].prio; |
154 return container[iimap[item]].prio; |
155 } |
155 } |
156 |
156 |
157 |
157 |
158 ///Deletes the item with minimum priority relative to \ref Compare. |
158 ///Deletes the item with minimum priority relative to \c Compare. |
159 |
159 |
160 /** |
160 /** |
161 This method deletes the item with minimum priority relative to \ref |
161 This method deletes the item with minimum priority relative to \c |
162 Compare from the heap. |
162 Compare from the heap. |
163 \pre The heap must be non-empty. |
163 \pre The heap must be non-empty. |
164 */ |
164 */ |
165 void pop(); |
165 void pop(); |
166 |
166 |
175 ///Decreases the priority of \c item to \c value. |
175 ///Decreases the priority of \c item to \c value. |
176 |
176 |
177 /** |
177 /** |
178 This method decreases the priority of \c item to \c value. |
178 This method decreases the priority of \c item to \c value. |
179 \pre \c item must be stored in the heap with priority at least \c |
179 \pre \c item must be stored in the heap with priority at least \c |
180 value relative to \ref Compare. |
180 value relative to \c Compare. |
181 */ |
181 */ |
182 void decrease (Item item, PrioType const value); |
182 void decrease (Item item, PrioType const value); |
183 |
183 |
184 ///Increases the priority of \c item to \c value. |
184 ///Increases the priority of \c item to \c value. |
185 |
185 |
186 /** |
186 /** |
187 This method sets the priority of \c item to \c value. Though |
187 This method sets the priority of \c item to \c value. Though |
188 there is no precondition on the priority of \c item, this |
188 there is no precondition on the priority of \c item, this |
189 method should be used only if it is indeed necessary to increase |
189 method should be used only if it is indeed necessary to increase |
190 (relative to \ref Compare) the priority of \c item, because this |
190 (relative to \c Compare) the priority of \c item, because this |
191 method is inefficient. |
191 method is inefficient. |
192 */ |
192 */ |
193 void increase (Item item, PrioType const value) { |
193 void increase (Item item, PrioType const value) { |
194 erase(item); |
194 erase(item); |
195 push(item, value); |
195 push(item, value); |