17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_FOURARY_HEAP_H |
19 #ifndef LEMON_FOURARY_HEAP_H |
20 #define LEMON_FOURARY_HEAP_H |
20 #define LEMON_FOURARY_HEAP_H |
21 |
21 |
22 ///\ingroup auxdat |
22 ///\ingroup heaps |
23 ///\file |
23 ///\file |
24 ///\brief 4ary Heap implementation. |
24 ///\brief Fourary heap implementation. |
25 |
25 |
26 #include <iostream> |
|
27 #include <vector> |
26 #include <vector> |
28 #include <utility> |
27 #include <utility> |
29 #include <functional> |
28 #include <functional> |
30 |
29 |
31 namespace lemon { |
30 namespace lemon { |
32 |
31 |
33 ///\ingroup auxdat |
32 /// \ingroup heaps |
34 /// |
33 /// |
35 ///\brief A 4ary Heap implementation. |
34 ///\brief Fourary heap data structure. |
36 /// |
35 /// |
37 ///This class implements the \e 4ary \e heap data structure. A \e heap |
36 /// This class implements the \e fourary \e heap data structure. |
38 ///is a data structure for storing items with specified values called \e |
37 /// It fully conforms to the \ref concepts::Heap "heap concept". |
39 ///priorities in such a way that finding the item with minimum priority is |
38 /// |
40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
39 /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap" |
41 ///one can change the priority of an item, add or erase an item, etc. |
40 /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap", |
42 /// |
41 /// but its nodes have at most four children, instead of two. |
43 ///\param _Prio Type of the priority of the items. |
42 /// |
44 ///\param _ItemIntMap A read and writable Item int map, used internally |
43 /// \tparam PR Type of the priorities of the items. |
45 ///to handle the cross references. |
44 /// \tparam IM A read-writable item map with \c int values, used |
46 ///\param _Compare A class for the ordering of the priorities. The |
45 /// internally to handle the cross references. |
47 ///default is \c std::less<_Prio>. |
46 /// \tparam CMP A functor class for comparing the priorities. |
48 /// |
47 /// The default is \c std::less<PR>. |
49 ///\sa FibHeap |
48 /// |
50 ///\sa Dijkstra |
49 ///\sa BinHeap |
51 ///\author Dorian Batha |
50 ///\sa KaryHeap |
52 |
51 #ifdef DOXYGEN |
53 template <typename _Prio, typename _ItemIntMap, |
52 template <typename PR, typename IM, typename CMP> |
54 typename _Compare = std::less<_Prio> > |
53 #else |
55 |
54 template <typename PR, typename IM, typename CMP = std::less<PR> > |
|
55 #endif |
56 class FouraryHeap { |
56 class FouraryHeap { |
57 |
|
58 public: |
57 public: |
59 ///\e |
58 /// Type of the item-int map. |
60 typedef _ItemIntMap ItemIntMap; |
59 typedef IM ItemIntMap; |
61 ///\e |
60 /// Type of the priorities. |
62 typedef _Prio Prio; |
61 typedef PR Prio; |
63 ///\e |
62 /// Type of the items stored in the heap. |
64 typedef typename ItemIntMap::Key Item; |
63 typedef typename ItemIntMap::Key Item; |
65 ///\e |
64 /// Type of the item-priority pairs. |
66 typedef std::pair<Item,Prio> Pair; |
65 typedef std::pair<Item,Prio> Pair; |
67 ///\e |
66 /// Functor type for comparing the priorities. |
68 typedef _Compare Compare; |
67 typedef CMP Compare; |
69 |
68 |
70 /// \brief Type to represent the items states. |
69 /// \brief Type to represent the states of the items. |
71 /// |
70 /// |
72 /// Each Item element have a state associated to it. It may be "in heap", |
71 /// Each item has a state associated to it. It can be "in heap", |
73 /// "pre heap" or "post heap". The latter two are indifferent from the |
72 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
74 /// heap's point of view, but may be useful to the user. |
73 /// heap's point of view, but may be useful to the user. |
75 /// |
74 /// |
76 /// The ItemIntMap \e should be initialized in such way that it maps |
75 /// The item-int map must be initialized in such way that it assigns |
77 /// PRE_HEAP (-1) to any element to be put in the heap... |
76 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
78 enum State { |
77 enum State { |
79 IN_HEAP = 0, |
78 IN_HEAP = 0, ///< = 0. |
80 PRE_HEAP = -1, |
79 PRE_HEAP = -1, ///< = -1. |
81 POST_HEAP = -2 |
80 POST_HEAP = -2 ///< = -2. |
82 }; |
81 }; |
83 |
82 |
84 private: |
83 private: |
85 std::vector<Pair> data; |
84 std::vector<Pair> _data; |
86 Compare comp; |
85 Compare _comp; |
87 ItemIntMap &iim; |
86 ItemIntMap &_iim; |
88 |
87 |
89 public: |
88 public: |
90 /// \brief The constructor. |
89 /// \brief Constructor. |
91 /// |
90 /// |
92 /// The constructor. |
91 /// Constructor. |
93 /// \param _iim should be given to the constructor, since it is used |
92 /// \param map A map that assigns \c int values to the items. |
94 /// internally to handle the cross references. The value of the map |
93 /// It is used internally to handle the cross references. |
95 /// should be PRE_HEAP (-1) for each element. |
94 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
96 explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {} |
95 explicit FouraryHeap(ItemIntMap &map) : _iim(map) {} |
97 |
96 |
98 /// \brief The constructor. |
97 /// \brief Constructor. |
99 /// |
98 /// |
100 /// The constructor. |
99 /// Constructor. |
101 /// \param _iim should be given to the constructor, since it is used |
100 /// \param map A map that assigns \c int values to the items. |
102 /// internally to handle the cross references. The value of the map |
101 /// It is used internally to handle the cross references. |
103 /// should be PRE_HEAP (-1) for each element. |
102 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
104 /// |
103 /// \param comp The function object used for comparing the priorities. |
105 /// \param _comp The comparator function object. |
104 FouraryHeap(ItemIntMap &map, const Compare &comp) |
106 FouraryHeap(ItemIntMap &_iim, const Compare &_comp) |
105 : _iim(map), _comp(comp) {} |
107 : iim(_iim), comp(_comp) {} |
106 |
108 |
107 /// \brief The number of items stored in the heap. |
109 /// The number of items stored in the heap. |
108 /// |
110 /// |
109 /// This function returns the number of items stored in the heap. |
111 /// \brief Returns the number of items stored in the heap. |
110 int size() const { return _data.size(); } |
112 int size() const { return data.size(); } |
111 |
113 |
112 /// \brief Check if the heap is empty. |
114 /// \brief Checks if the heap stores no items. |
113 /// |
115 /// |
114 /// This function returns \c true if the heap is empty. |
116 /// Returns \c true if and only if the heap stores no items. |
115 bool empty() const { return _data.empty(); } |
117 bool empty() const { return data.empty(); } |
116 |
118 |
117 /// \brief Make the heap empty. |
119 /// \brief Make empty this heap. |
118 /// |
120 /// |
119 /// This functon makes the heap empty. |
121 /// Make empty this heap. It does not change the cross reference map. |
120 /// It does not change the cross reference map. If you want to reuse |
122 /// If you want to reuse what is not surely empty you should first clear |
121 /// a heap that is not surely empty, you should first clear it and |
123 /// the heap and after that you should set the cross reference map for |
122 /// then you should set the cross reference map to \c PRE_HEAP |
124 /// each item to \c PRE_HEAP. |
123 /// for each item. |
125 void clear() { data.clear(); } |
124 void clear() { _data.clear(); } |
126 |
125 |
127 private: |
126 private: |
128 static int parent(int i) { return (i-1)/4; } |
127 static int parent(int i) { return (i-1)/4; } |
129 static int firstChild(int i) { return 4*i+1; } |
128 static int firstChild(int i) { return 4*i+1; } |
130 |
129 |
131 bool less(const Pair &p1, const Pair &p2) const { |
130 bool less(const Pair &p1, const Pair &p2) const { |
132 return comp(p1.second, p2.second); |
131 return _comp(p1.second, p2.second); |
133 } |
132 } |
134 |
133 |
135 int find_min(const int child, const int length) { |
134 int findMin(const int child, const int length) { |
136 int min=child; |
135 int min=child; |
137 if( child+3<length ) { |
136 if( child+3<length ) { |
138 if( less(data[child+3], data[min]) ) |
137 if( less(_data[child+3], _data[min]) ) |
139 min=child+3; |
138 min=child+3; |
140 if( less(data[child+2], data[min]) ) |
139 if( less(_data[child+2], _data[min]) ) |
141 min=child+2; |
140 min=child+2; |
142 if( less(data[child+1], data[min]) ) |
141 if( less(_data[child+1], _data[min]) ) |
143 min=child+1; |
142 min=child+1; |
144 } |
143 } |
145 else if( child+2<length ) { |
144 else if( child+2<length ) { |
146 if( less(data[child+2], data[min]) ) |
145 if( less(_data[child+2], _data[min]) ) |
147 min=child+2; |
146 min=child+2; |
148 if( less(data[child+1], data[min]) ) |
147 if( less(_data[child+1], _data[min]) ) |
149 min=child+1; |
148 min=child+1; |
150 } |
149 } |
151 else if( child+1<length ) { |
150 else if( child+1<length ) { |
152 if( less(data[child+1], data[min]) ) |
151 if( less(_data[child+1], _data[min]) ) |
153 min=child+1; |
152 min=child+1; |
154 } |
153 } |
155 return min; |
154 return min; |
156 } |
155 } |
157 |
156 |
158 void bubble_up(int hole, Pair p) { |
157 void bubbleUp(int hole, Pair p) { |
159 int par = parent(hole); |
158 int par = parent(hole); |
160 while( hole>0 && less(p,data[par]) ) { |
159 while( hole>0 && less(p,_data[par]) ) { |
161 move(data[par],hole); |
160 move(_data[par],hole); |
162 hole = par; |
161 hole = par; |
163 par = parent(hole); |
162 par = parent(hole); |
164 } |
163 } |
165 move(p, hole); |
164 move(p, hole); |
166 } |
165 } |
167 |
166 |
168 void bubble_down(int hole, Pair p, int length) { |
167 void bubbleDown(int hole, Pair p, int length) { |
169 int child = firstChild(hole); |
168 int child = firstChild(hole); |
170 while( child<length && length>1 ) { |
169 while( child<length && length>1 ) { |
171 child = find_min(child,length); |
170 child = findMin(child,length); |
172 if( !less(data[child], p) ) |
171 if( !less(_data[child], p) ) |
173 goto ok; |
172 goto ok; |
174 move(data[child], hole); |
173 move(_data[child], hole); |
175 hole = child; |
174 hole = child; |
176 child = firstChild(hole); |
175 child = firstChild(hole); |
177 } |
176 } |
178 ok: |
177 ok: |
179 move(p, hole); |
178 move(p, hole); |
180 } |
179 } |
181 |
180 |
182 void move(const Pair &p, int i) { |
181 void move(const Pair &p, int i) { |
183 data[i] = p; |
182 _data[i] = p; |
184 iim.set(p.first, i); |
183 _iim.set(p.first, i); |
185 } |
184 } |
186 |
185 |
187 public: |
186 public: |
188 |
|
189 /// \brief Insert a pair of item and priority into the heap. |
187 /// \brief Insert a pair of item and priority into the heap. |
190 /// |
188 /// |
191 /// Adds \c p.first to the heap with priority \c p.second. |
189 /// This function inserts \c p.first to the heap with priority |
|
190 /// \c p.second. |
192 /// \param p The pair to insert. |
191 /// \param p The pair to insert. |
|
192 /// \pre \c p.first must not be stored in the heap. |
193 void push(const Pair &p) { |
193 void push(const Pair &p) { |
194 int n = data.size(); |
194 int n = _data.size(); |
195 data.resize(n+1); |
195 _data.resize(n+1); |
196 bubble_up(n, p); |
196 bubbleUp(n, p); |
197 } |
197 } |
198 |
198 |
199 /// \brief Insert an item into the heap with the given heap. |
199 /// \brief Insert an item into the heap with the given priority. |
200 /// |
200 /// |
201 /// Adds \c i to the heap with priority \c p. |
201 /// This function inserts the given item into the heap with the |
|
202 /// given priority. |
202 /// \param i The item to insert. |
203 /// \param i The item to insert. |
203 /// \param p The priority of the item. |
204 /// \param p The priority of the item. |
|
205 /// \pre \e i must not be stored in the heap. |
204 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } |
206 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } |
205 |
207 |
206 /// \brief Returns the item with minimum priority relative to \c Compare. |
208 /// \brief Return the item having minimum priority. |
207 /// |
209 /// |
208 /// This method returns the item with minimum priority relative to \c |
210 /// This function returns the item having minimum priority. |
209 /// Compare. |
211 /// \pre The heap must be non-empty. |
210 /// \pre The heap must be nonempty. |
212 Item top() const { return _data[0].first; } |
211 Item top() const { return data[0].first; } |
213 |
212 |
214 /// \brief The minimum priority. |
213 /// \brief Returns the minimum priority relative to \c Compare. |
215 /// |
214 /// |
216 /// This function returns the minimum priority. |
215 /// It returns the minimum priority relative to \c Compare. |
217 /// \pre The heap must be non-empty. |
216 /// \pre The heap must be nonempty. |
218 Prio prio() const { return _data[0].second; } |
217 Prio prio() const { return data[0].second; } |
219 |
218 |
220 /// \brief Remove the item having minimum priority. |
219 /// \brief Deletes the item with minimum priority relative to \c Compare. |
221 /// |
220 /// |
222 /// This function removes the item having minimum priority. |
221 /// This method deletes the item with minimum priority relative to \c |
|
222 /// Compare from the heap. |
|
223 /// \pre The heap must be non-empty. |
223 /// \pre The heap must be non-empty. |
224 void pop() { |
224 void pop() { |
225 int n = data.size()-1; |
225 int n = _data.size()-1; |
226 iim.set(data[0].first, POST_HEAP); |
226 _iim.set(_data[0].first, POST_HEAP); |
227 if (n>0) bubble_down(0, data[n], n); |
227 if (n>0) bubbleDown(0, _data[n], n); |
228 data.pop_back(); |
228 _data.pop_back(); |
229 } |
229 } |
230 |
230 |
231 /// \brief Deletes \c i from the heap. |
231 /// \brief Remove the given item from the heap. |
232 /// |
232 /// |
233 /// This method deletes item \c i from the heap. |
233 /// This function removes the given item from the heap if it is |
234 /// \param i The item to erase. |
234 /// already stored. |
235 /// \pre The item should be in the heap. |
235 /// \param i The item to delete. |
|
236 /// \pre \e i must be in the heap. |
236 void erase(const Item &i) { |
237 void erase(const Item &i) { |
237 int h = iim[i]; |
238 int h = _iim[i]; |
238 int n = data.size()-1; |
239 int n = _data.size()-1; |
239 iim.set(data[h].first, POST_HEAP); |
240 _iim.set(_data[h].first, POST_HEAP); |
240 if( h<n ) { |
241 if( h<n ) { |
241 if( less(data[parent(h)], data[n]) ) |
242 if( less(_data[parent(h)], _data[n]) ) |
242 bubble_down(h, data[n], n); |
243 bubbleDown(h, _data[n], n); |
243 else |
244 else |
244 bubble_up(h, data[n]); |
245 bubbleUp(h, _data[n]); |
245 } |
246 } |
246 data.pop_back(); |
247 _data.pop_back(); |
247 } |
248 } |
248 |
249 |
249 /// \brief Returns the priority of \c i. |
250 /// \brief The priority of the given item. |
250 /// |
251 /// |
251 /// This function returns the priority of item \c i. |
252 /// This function returns the priority of the given item. |
252 /// \pre \c i must be in the heap. |
253 /// \param i The item. |
253 /// \param i The item. |
254 /// \pre \e i must be in the heap. |
254 Prio operator[](const Item &i) const { |
255 Prio operator[](const Item &i) const { |
255 int idx = iim[i]; |
256 int idx = _iim[i]; |
256 return data[idx].second; |
257 return _data[idx].second; |
257 } |
258 } |
258 |
259 |
259 /// \brief \c i gets to the heap with priority \c p independently |
260 /// \brief Set the priority of an item or insert it, if it is |
260 /// if \c i was already there. |
261 /// not stored in the heap. |
261 /// |
262 /// |
262 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
263 /// This method sets the priority of the given item if it is |
263 /// in the heap and sets the priority of \c i to \c p otherwise. |
264 /// already stored in the heap. Otherwise it inserts the given |
|
265 /// item into the heap with the given priority. |
264 /// \param i The item. |
266 /// \param i The item. |
265 /// \param p The priority. |
267 /// \param p The priority. |
266 void set(const Item &i, const Prio &p) { |
268 void set(const Item &i, const Prio &p) { |
267 int idx = iim[i]; |
269 int idx = _iim[i]; |
268 if( idx < 0 ) |
270 if( idx < 0 ) |
269 push(i,p); |
271 push(i,p); |
270 else if( comp(p, data[idx].second) ) |
272 else if( _comp(p, _data[idx].second) ) |
271 bubble_up(idx, Pair(i,p)); |
273 bubbleUp(idx, Pair(i,p)); |
272 else |
274 else |
273 bubble_down(idx, Pair(i,p), data.size()); |
275 bubbleDown(idx, Pair(i,p), _data.size()); |
274 } |
276 } |
275 |
277 |
276 /// \brief Decreases the priority of \c i to \c p. |
278 /// \brief Decrease the priority of an item to the given value. |
277 /// |
279 /// |
278 /// This method decreases the priority of item \c i to \c p. |
280 /// This function decreases the priority of an item to the given value. |
279 /// \pre \c i must be stored in the heap with priority at least \c |
|
280 /// p relative to \c Compare. |
|
281 /// \param i The item. |
281 /// \param i The item. |
282 /// \param p The priority. |
282 /// \param p The priority. |
|
283 /// \pre \e i must be stored in the heap with priority at least \e p. |
283 void decrease(const Item &i, const Prio &p) { |
284 void decrease(const Item &i, const Prio &p) { |
284 int idx = iim[i]; |
285 int idx = _iim[i]; |
285 bubble_up(idx, Pair(i,p)); |
286 bubbleUp(idx, Pair(i,p)); |
286 } |
287 } |
287 |
288 |
288 /// \brief Increases the priority of \c i to \c p. |
289 /// \brief Increase the priority of an item to the given value. |
289 /// |
290 /// |
290 /// This method sets the priority of item \c i to \c p. |
291 /// This function increases the priority of an item to the given value. |
291 /// \pre \c i must be stored in the heap with priority at most \c |
|
292 /// p relative to \c Compare. |
|
293 /// \param i The item. |
292 /// \param i The item. |
294 /// \param p The priority. |
293 /// \param p The priority. |
|
294 /// \pre \e i must be stored in the heap with priority at most \e p. |
295 void increase(const Item &i, const Prio &p) { |
295 void increase(const Item &i, const Prio &p) { |
296 int idx = iim[i]; |
296 int idx = _iim[i]; |
297 bubble_down(idx, Pair(i,p), data.size()); |
297 bubbleDown(idx, Pair(i,p), _data.size()); |
298 } |
298 } |
299 |
299 |
300 /// \brief Returns if \c item is in, has already been in, or has |
300 /// \brief Return the state of an item. |
301 /// never been in the heap. |
301 /// |
302 /// |
302 /// This method returns \c PRE_HEAP if the given item has never |
303 /// This method returns PRE_HEAP if \c item has never been in the |
303 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
304 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
304 /// and \c POST_HEAP otherwise. |
305 /// otherwise. In the latter case it is possible that \c item will |
305 /// In the latter case it is possible that the item will get back |
306 /// get back to the heap again. |
306 /// to the heap again. |
307 /// \param i The item. |
307 /// \param i The item. |
308 State state(const Item &i) const { |
308 State state(const Item &i) const { |
309 int s = iim[i]; |
309 int s = _iim[i]; |
310 if (s>=0) s=0; |
310 if (s>=0) s=0; |
311 return State(s); |
311 return State(s); |
312 } |
312 } |
313 |
313 |
314 /// \brief Sets the state of the \c item in the heap. |
314 /// \brief Set the state of an item in the heap. |
315 /// |
315 /// |
316 /// Sets the state of the \c item in the heap. It can be used to |
316 /// This function sets the state of the given item in the heap. |
317 /// manually clear the heap when it is important to achive the |
317 /// It can be used to manually clear the heap when it is important |
318 /// better time complexity. |
318 /// to achive better time complexity. |
319 /// \param i The item. |
319 /// \param i The item. |
320 /// \param st The state. It should not be \c IN_HEAP. |
320 /// \param st The state. It should not be \c IN_HEAP. |
321 void state(const Item& i, State st) { |
321 void state(const Item& i, State st) { |
322 switch (st) { |
322 switch (st) { |
323 case POST_HEAP: |
323 case POST_HEAP: |
324 case PRE_HEAP: |
324 case PRE_HEAP: |
325 if (state(i) == IN_HEAP) erase(i); |
325 if (state(i) == IN_HEAP) erase(i); |
326 iim[i] = st; |
326 _iim[i] = st; |
327 break; |
327 break; |
328 case IN_HEAP: |
328 case IN_HEAP: |
329 break; |
329 break; |
330 } |
330 } |
331 } |
331 } |
332 |
332 |
333 /// \brief Replaces an item in the heap. |
333 /// \brief Replace an item in the heap. |
334 /// |
334 /// |
335 /// The \c i item is replaced with \c j item. The \c i item should |
335 /// This function replaces item \c i with item \c j. |
336 /// be in the heap, while the \c j should be out of the heap. The |
336 /// Item \c i must be in the heap, while \c j must be out of the heap. |
337 /// \c i item will out of the heap and \c j will be in the heap |
337 /// After calling this method, item \c i will be out of the |
338 /// with the same prioriority as prevoiusly the \c i item. |
338 /// heap and \c j will be in the heap with the same prioriority |
|
339 /// as item \c i had before. |
339 void replace(const Item& i, const Item& j) { |
340 void replace(const Item& i, const Item& j) { |
340 int idx = iim[i]; |
341 int idx = _iim[i]; |
341 iim.set(i, iim[j]); |
342 _iim.set(i, _iim[j]); |
342 iim.set(j, idx); |
343 _iim.set(j, idx); |
343 data[idx].first = j; |
344 _data[idx].first = j; |
344 } |
345 } |
345 |
346 |
346 }; // class FouraryHeap |
347 }; // class FouraryHeap |
347 |
348 |
348 } // namespace lemon |
349 } // namespace lemon |