19 #ifndef LEMON_FIB_HEAP_H |
19 #ifndef LEMON_FIB_HEAP_H |
20 #define LEMON_FIB_HEAP_H |
20 #define LEMON_FIB_HEAP_H |
21 |
21 |
22 ///\file |
22 ///\file |
23 ///\ingroup auxdat |
23 ///\ingroup auxdat |
24 ///\brief Fibonacci Heap implementation. |
24 ///\brief Fibonacci heap implementation. |
25 |
25 |
26 #include <vector> |
26 #include <vector> |
|
27 #include <utility> |
27 #include <functional> |
28 #include <functional> |
28 #include <lemon/math.h> |
29 #include <lemon/math.h> |
29 |
30 |
30 namespace lemon { |
31 namespace lemon { |
31 |
32 |
32 /// \ingroup auxdat |
33 /// \ingroup auxdat |
33 /// |
34 /// |
34 ///\brief Fibonacci Heap. |
35 /// \brief Fibonacci heap data structure. |
35 /// |
36 /// |
36 ///This class implements the \e Fibonacci \e heap data structure. A \e heap |
37 /// This class implements the \e Fibonacci \e heap data structure. |
37 ///is a data structure for storing items with specified values called \e |
38 /// It fully conforms to the \ref concepts::Heap "heap concept". |
38 ///priorities in such a way that finding the item with minimum priority is |
|
39 ///efficient. \c CMP specifies the ordering of the priorities. In a heap |
|
40 ///one can change the priority of an item, add or erase an item, etc. |
|
41 /// |
39 /// |
42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
40 /// The methods \ref increase() and \ref erase() are not efficient in a |
43 ///heap. In case of many calls to these operations, it is better to use a |
41 /// Fibonacci heap. In case of many calls of these operations, it is |
44 ///\ref BinHeap "binary heap". |
42 /// better to use other heap structure, e.g. \ref BinHeap "binary heap". |
45 /// |
43 /// |
46 ///\param PRIO Type of the priority of the items. |
44 /// \tparam PR Type of the priorities of the items. |
47 ///\param IM A read and writable Item int map, used internally |
45 /// \tparam IM A read-writable item map with \c int values, used |
48 ///to handle the cross references. |
46 /// internally to handle the cross references. |
49 ///\param CMP A class for the ordering of the priorities. The |
47 /// \tparam CMP A functor class for comparing the priorities. |
50 ///default is \c std::less<PRIO>. |
48 /// The default is \c std::less<PR>. |
51 /// |
|
52 ///\sa BinHeap |
|
53 ///\sa Dijkstra |
|
54 #ifdef DOXYGEN |
49 #ifdef DOXYGEN |
55 template <typename PRIO, typename IM, typename CMP> |
50 template <typename PR, typename IM, typename CMP> |
56 #else |
51 #else |
57 template <typename PRIO, typename IM, typename CMP = std::less<PRIO> > |
52 template <typename PR, typename IM, typename CMP = std::less<PR> > |
58 #endif |
53 #endif |
59 class FibHeap { |
54 class FibHeap { |
60 public: |
55 public: |
61 ///\e |
56 |
|
57 /// Type of the item-int map. |
62 typedef IM ItemIntMap; |
58 typedef IM ItemIntMap; |
63 ///\e |
59 /// Type of the priorities. |
64 typedef PRIO Prio; |
60 typedef PR Prio; |
65 ///\e |
61 /// Type of the items stored in the heap. |
66 typedef typename ItemIntMap::Key Item; |
62 typedef typename ItemIntMap::Key Item; |
67 ///\e |
63 /// Type of the item-priority pairs. |
68 typedef std::pair<Item,Prio> Pair; |
64 typedef std::pair<Item,Prio> Pair; |
69 ///\e |
65 /// Functor type for comparing the priorities. |
70 typedef CMP Compare; |
66 typedef CMP Compare; |
71 |
67 |
72 private: |
68 private: |
73 class Store; |
69 class Store; |
74 |
70 |
78 Compare _comp; |
74 Compare _comp; |
79 int _num; |
75 int _num; |
80 |
76 |
81 public: |
77 public: |
82 |
78 |
83 /// \brief Type to represent the items states. |
79 /// \brief Type to represent the states of the items. |
84 /// |
80 /// |
85 /// Each Item element have a state associated to it. It may be "in heap", |
81 /// Each item has a state associated to it. It can be "in heap", |
86 /// "pre heap" or "post heap". The latter two are indifferent from the |
82 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
87 /// heap's point of view, but may be useful to the user. |
83 /// heap's point of view, but may be useful to the user. |
88 /// |
84 /// |
89 /// The item-int map must be initialized in such way that it assigns |
85 /// The item-int map must be initialized in such way that it assigns |
90 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
86 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
91 enum State { |
87 enum State { |
92 IN_HEAP = 0, ///< = 0. |
88 IN_HEAP = 0, ///< = 0. |
93 PRE_HEAP = -1, ///< = -1. |
89 PRE_HEAP = -1, ///< = -1. |
94 POST_HEAP = -2 ///< = -2. |
90 POST_HEAP = -2 ///< = -2. |
95 }; |
91 }; |
96 |
92 |
97 /// \brief The constructor |
93 /// \brief Constructor. |
98 /// |
94 /// |
99 /// \c map should be given to the constructor, since it is |
95 /// Constructor. |
100 /// used internally to handle the cross references. |
96 /// \param map A map that assigns \c int values to the items. |
|
97 /// It is used internally to handle the cross references. |
|
98 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
101 explicit FibHeap(ItemIntMap &map) |
99 explicit FibHeap(ItemIntMap &map) |
102 : _minimum(0), _iim(map), _num() {} |
100 : _minimum(0), _iim(map), _num() {} |
103 |
101 |
104 /// \brief The constructor |
102 /// \brief Constructor. |
105 /// |
103 /// |
106 /// \c map should be given to the constructor, since it is used |
104 /// Constructor. |
107 /// internally to handle the cross references. \c comp is an |
105 /// \param map A map that assigns \c int values to the items. |
108 /// object for ordering of the priorities. |
106 /// It is used internally to handle the cross references. |
|
107 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
|
108 /// \param comp The function object used for comparing the priorities. |
109 FibHeap(ItemIntMap &map, const Compare &comp) |
109 FibHeap(ItemIntMap &map, const Compare &comp) |
110 : _minimum(0), _iim(map), _comp(comp), _num() {} |
110 : _minimum(0), _iim(map), _comp(comp), _num() {} |
111 |
111 |
112 /// \brief The number of items stored in the heap. |
112 /// \brief The number of items stored in the heap. |
113 /// |
113 /// |
114 /// Returns the number of items stored in the heap. |
114 /// This function returns the number of items stored in the heap. |
115 int size() const { return _num; } |
115 int size() const { return _num; } |
116 |
116 |
117 /// \brief Checks if the heap stores no items. |
117 /// \brief Check if the heap is empty. |
118 /// |
118 /// |
119 /// Returns \c true if and only if the heap stores no items. |
119 /// This function returns \c true if the heap is empty. |
120 bool empty() const { return _num==0; } |
120 bool empty() const { return _num==0; } |
121 |
121 |
122 /// \brief Make empty this heap. |
122 /// \brief Make the heap empty. |
123 /// |
123 /// |
124 /// Make empty this heap. It does not change the cross reference |
124 /// This functon makes the heap empty. |
125 /// map. If you want to reuse a heap what is not surely empty you |
125 /// It does not change the cross reference map. If you want to reuse |
126 /// should first clear the heap and after that you should set the |
126 /// a heap that is not surely empty, you should first clear it and |
127 /// cross reference map for each item to \c PRE_HEAP. |
127 /// then you should set the cross reference map to \c PRE_HEAP |
|
128 /// for each item. |
128 void clear() { |
129 void clear() { |
129 _data.clear(); _minimum = 0; _num = 0; |
130 _data.clear(); _minimum = 0; _num = 0; |
130 } |
131 } |
131 |
132 |
132 /// \brief \c item gets to the heap with priority \c value independently |
133 /// \brief Insert an item into the heap with the given priority. |
133 /// if \c item was already there. |
134 /// |
134 /// |
135 /// This function inserts the given item into the heap with the |
135 /// This method calls \ref push(\c item, \c value) if \c item is not |
136 /// given priority. |
136 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
137 /// \param item The item to insert. |
137 /// \ref increase(\c item, \c value) otherwise. |
138 /// \param prio The priority of the item. |
138 void set (const Item& item, const Prio& value) { |
139 /// \pre \e item must not be stored in the heap. |
139 int i=_iim[item]; |
140 void push (const Item& item, const Prio& prio) { |
140 if ( i >= 0 && _data[i].in ) { |
|
141 if ( _comp(value, _data[i].prio) ) decrease(item, value); |
|
142 if ( _comp(_data[i].prio, value) ) increase(item, value); |
|
143 } else push(item, value); |
|
144 } |
|
145 |
|
146 /// \brief Adds \c item to the heap with priority \c value. |
|
147 /// |
|
148 /// Adds \c item to the heap with priority \c value. |
|
149 /// \pre \c item must not be stored in the heap. |
|
150 void push (const Item& item, const Prio& value) { |
|
151 int i=_iim[item]; |
141 int i=_iim[item]; |
152 if ( i < 0 ) { |
142 if ( i < 0 ) { |
153 int s=_data.size(); |
143 int s=_data.size(); |
154 _iim.set( item, s ); |
144 _iim.set( item, s ); |
155 Store st; |
145 Store st; |
166 if ( _num ) { |
156 if ( _num ) { |
167 _data[_data[_minimum].right_neighbor].left_neighbor=i; |
157 _data[_data[_minimum].right_neighbor].left_neighbor=i; |
168 _data[i].right_neighbor=_data[_minimum].right_neighbor; |
158 _data[i].right_neighbor=_data[_minimum].right_neighbor; |
169 _data[_minimum].right_neighbor=i; |
159 _data[_minimum].right_neighbor=i; |
170 _data[i].left_neighbor=_minimum; |
160 _data[i].left_neighbor=_minimum; |
171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i; |
161 if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; |
172 } else { |
162 } else { |
173 _data[i].right_neighbor=_data[i].left_neighbor=i; |
163 _data[i].right_neighbor=_data[i].left_neighbor=i; |
174 _minimum=i; |
164 _minimum=i; |
175 } |
165 } |
176 _data[i].prio=value; |
166 _data[i].prio=prio; |
177 ++_num; |
167 ++_num; |
178 } |
168 } |
179 |
169 |
180 /// \brief Returns the item with minimum priority relative to \c Compare. |
170 /// \brief Return the item having minimum priority. |
181 /// |
171 /// |
182 /// This method returns the item with minimum priority relative to \c |
172 /// This function returns the item having minimum priority. |
183 /// Compare. |
173 /// \pre The heap must be non-empty. |
184 /// \pre The heap must be nonempty. |
|
185 Item top() const { return _data[_minimum].name; } |
174 Item top() const { return _data[_minimum].name; } |
186 |
175 |
187 /// \brief Returns the minimum priority relative to \c Compare. |
176 /// \brief The minimum priority. |
188 /// |
177 /// |
189 /// It returns the minimum priority relative to \c Compare. |
178 /// This function returns the minimum priority. |
190 /// \pre The heap must be nonempty. |
179 /// \pre The heap must be non-empty. |
191 const Prio& prio() const { return _data[_minimum].prio; } |
180 Prio prio() const { return _data[_minimum].prio; } |
192 |
181 |
193 /// \brief Returns the priority of \c item. |
182 /// \brief Remove the item having minimum priority. |
194 /// |
183 /// |
195 /// It returns the priority of \c item. |
184 /// This function removes the item having minimum priority. |
196 /// \pre \c item must be in the heap. |
|
197 const Prio& operator[](const Item& item) const { |
|
198 return _data[_iim[item]].prio; |
|
199 } |
|
200 |
|
201 /// \brief Deletes the item with minimum priority relative to \c Compare. |
|
202 /// |
|
203 /// This method deletes the item with minimum priority relative to \c |
|
204 /// Compare from the heap. |
|
205 /// \pre The heap must be non-empty. |
185 /// \pre The heap must be non-empty. |
206 void pop() { |
186 void pop() { |
207 /*The first case is that there are only one root.*/ |
187 /*The first case is that there are only one root.*/ |
208 if ( _data[_minimum].left_neighbor==_minimum ) { |
188 if ( _data[_minimum].left_neighbor==_minimum ) { |
209 _data[_minimum].in=false; |
189 _data[_minimum].in=false; |
250 _minimum=i; //As if its prio would be -infinity |
232 _minimum=i; //As if its prio would be -infinity |
251 pop(); |
233 pop(); |
252 } |
234 } |
253 } |
235 } |
254 |
236 |
255 /// \brief Decreases the priority of \c item to \c value. |
237 /// \brief The priority of the given item. |
256 /// |
238 /// |
257 /// This method decreases the priority of \c item to \c value. |
239 /// This function returns the priority of the given item. |
258 /// \pre \c item must be stored in the heap with priority at least \c |
240 /// \param item The item. |
259 /// value relative to \c Compare. |
241 /// \pre \e item must be in the heap. |
260 void decrease (Item item, const Prio& value) { |
242 Prio operator[](const Item& item) const { |
|
243 return _data[_iim[item]].prio; |
|
244 } |
|
245 |
|
246 /// \brief Set the priority of an item or insert it, if it is |
|
247 /// not stored in the heap. |
|
248 /// |
|
249 /// This method sets the priority of the given item if it is |
|
250 /// already stored in the heap. Otherwise it inserts the given |
|
251 /// item into the heap with the given priority. |
|
252 /// \param item The item. |
|
253 /// \param prio The priority. |
|
254 void set (const Item& item, const Prio& prio) { |
261 int i=_iim[item]; |
255 int i=_iim[item]; |
262 _data[i].prio=value; |
256 if ( i >= 0 && _data[i].in ) { |
|
257 if ( _comp(prio, _data[i].prio) ) decrease(item, prio); |
|
258 if ( _comp(_data[i].prio, prio) ) increase(item, prio); |
|
259 } else push(item, prio); |
|
260 } |
|
261 |
|
262 /// \brief Decrease the priority of an item to the given value. |
|
263 /// |
|
264 /// This function decreases the priority of an item to the given value. |
|
265 /// \param item The item. |
|
266 /// \param prio The priority. |
|
267 /// \pre \e item must be stored in the heap with priority at least \e prio. |
|
268 void decrease (const Item& item, const Prio& prio) { |
|
269 int i=_iim[item]; |
|
270 _data[i].prio=prio; |
263 int p=_data[i].parent; |
271 int p=_data[i].parent; |
264 |
272 |
265 if ( p!=-1 && _comp(value, _data[p].prio) ) { |
273 if ( p!=-1 && _comp(prio, _data[p].prio) ) { |
266 cut(i,p); |
274 cut(i,p); |
267 cascade(p); |
275 cascade(p); |
268 } |
276 } |
269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; |
277 if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; |
270 } |
278 } |
271 |
279 |
272 /// \brief Increases the priority of \c item to \c value. |
280 /// \brief Increase the priority of an item to the given value. |
273 /// |
281 /// |
274 /// This method sets the priority of \c item to \c value. Though |
282 /// This function increases the priority of an item to the given value. |
275 /// there is no precondition on the priority of \c item, this |
283 /// \param item The item. |
276 /// method should be used only if it is indeed necessary to increase |
284 /// \param prio The priority. |
277 /// (relative to \c Compare) the priority of \c item, because this |
285 /// \pre \e item must be stored in the heap with priority at most \e prio. |
278 /// method is inefficient. |
286 void increase (const Item& item, const Prio& prio) { |
279 void increase (Item item, const Prio& value) { |
|
280 erase(item); |
287 erase(item); |
281 push(item, value); |
288 push(item, prio); |
282 } |
289 } |
283 |
290 |
284 |
291 /// \brief Return the state of an item. |
285 /// \brief Returns if \c item is in, has already been in, or has never |
292 /// |
286 /// been in the heap. |
293 /// This method returns \c PRE_HEAP if the given item has never |
287 /// |
294 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
288 /// This method returns PRE_HEAP if \c item has never been in the |
295 /// and \c POST_HEAP otherwise. |
289 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
296 /// In the latter case it is possible that the item will get back |
290 /// otherwise. In the latter case it is possible that \c item will |
297 /// to the heap again. |
291 /// get back to the heap again. |
298 /// \param item The item. |
292 State state(const Item &item) const { |
299 State state(const Item &item) const { |
293 int i=_iim[item]; |
300 int i=_iim[item]; |
294 if( i>=0 ) { |
301 if( i>=0 ) { |
295 if ( _data[i].in ) i=0; |
302 if ( _data[i].in ) i=0; |
296 else i=-2; |
303 else i=-2; |
297 } |
304 } |
298 return State(i); |
305 return State(i); |
299 } |
306 } |
300 |
307 |
301 /// \brief Sets the state of the \c item in the heap. |
308 /// \brief Set the state of an item in the heap. |
302 /// |
309 /// |
303 /// Sets the state of the \c item in the heap. It can be used to |
310 /// This function sets the state of the given item in the heap. |
304 /// manually clear the heap when it is important to achive the |
311 /// It can be used to manually clear the heap when it is important |
305 /// better time _complexity. |
312 /// to achive better time complexity. |
306 /// \param i The item. |
313 /// \param i The item. |
307 /// \param st The state. It should not be \c IN_HEAP. |
314 /// \param st The state. It should not be \c IN_HEAP. |
308 void state(const Item& i, State st) { |
315 void state(const Item& i, State st) { |
309 switch (st) { |
316 switch (st) { |
310 case POST_HEAP: |
317 case POST_HEAP: |