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