18 |
18 |
19 #ifndef LEMON_BINOM_HEAP_H |
19 #ifndef LEMON_BINOM_HEAP_H |
20 #define LEMON_BINOM_HEAP_H |
20 #define LEMON_BINOM_HEAP_H |
21 |
21 |
22 ///\file |
22 ///\file |
23 ///\ingroup auxdat |
23 ///\ingroup heaps |
24 ///\brief Binomial Heap implementation. |
24 ///\brief Binomial 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 #include <lemon/counter.h> |
30 #include <lemon/counter.h> |
30 |
31 |
31 namespace lemon { |
32 namespace lemon { |
32 |
33 |
33 /// \ingroup auxdat |
34 /// \ingroup heaps |
34 /// |
35 /// |
35 ///\brief Binomial Heap. |
36 ///\brief Binomial heap data structure. |
36 /// |
37 /// |
37 ///This class implements the \e Binomial \e heap data structure. A \e heap |
38 /// This class implements the \e binomial \e heap data structure. |
38 ///is a data structure for storing items with specified values called \e |
39 /// It fully conforms to the \ref concepts::Heap "heap concept". |
39 ///priorities in such a way that finding the item with minimum priority is |
|
40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
|
41 ///one can change the priority of an item, add or erase an item, etc. |
|
42 /// |
40 /// |
43 ///The methods \ref increase and \ref erase are not efficient in a Binomial |
41 /// The methods \ref increase() and \ref erase() are not efficient |
44 ///heap. In case of many calls to these operations, it is better to use a |
42 /// in a binomial heap. In case of many calls of these operations, |
45 ///\ref BinHeap "binary heap". |
43 /// it is better to use other heap structure, e.g. \ref BinHeap |
|
44 /// "binary heap". |
46 /// |
45 /// |
47 ///\param _Prio Type of the priority of the items. |
46 /// \tparam PR Type of the priorities of the items. |
48 ///\param _ItemIntMap A read and writable Item int map, used internally |
47 /// \tparam IM A read-writable item map with \c int values, used |
49 ///to handle the cross references. |
48 /// internally to handle the cross references. |
50 ///\param _Compare A class for the ordering of the priorities. The |
49 /// \tparam CMP A functor class for comparing the priorities. |
51 ///default is \c std::less<_Prio>. |
50 /// The default is \c std::less<PR>. |
52 /// |
|
53 ///\sa BinHeap |
|
54 ///\sa Dijkstra |
|
55 ///\author Dorian Batha |
|
56 |
|
57 #ifdef DOXYGEN |
51 #ifdef DOXYGEN |
58 template <typename _Prio, |
52 template <typename PR, typename IM, typename CMP> |
59 typename _ItemIntMap, |
|
60 typename _Compare> |
|
61 #else |
53 #else |
62 template <typename _Prio, |
54 template <typename PR, typename IM, typename CMP = std::less<PR> > |
63 typename _ItemIntMap, |
|
64 typename _Compare = std::less<_Prio> > |
|
65 #endif |
55 #endif |
66 class BinomHeap { |
56 class BinomHeap { |
67 public: |
57 public: |
68 typedef _ItemIntMap ItemIntMap; |
58 /// Type of the item-int map. |
69 typedef _Prio Prio; |
59 typedef IM ItemIntMap; |
|
60 /// Type of the priorities. |
|
61 typedef PR Prio; |
|
62 /// Type of the items stored in the heap. |
70 typedef typename ItemIntMap::Key Item; |
63 typedef typename ItemIntMap::Key Item; |
71 typedef std::pair<Item,Prio> Pair; |
64 /// Functor type for comparing the priorities. |
72 typedef _Compare Compare; |
65 typedef CMP Compare; |
|
66 |
|
67 /// \brief Type to represent the states of the items. |
|
68 /// |
|
69 /// Each item has a state associated to it. It can be "in heap", |
|
70 /// "pre-heap" or "post-heap". The latter two are indifferent from the |
|
71 /// heap's point of view, but may be useful to the user. |
|
72 /// |
|
73 /// The item-int map must be initialized in such way that it assigns |
|
74 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. |
|
75 enum State { |
|
76 IN_HEAP = 0, ///< = 0. |
|
77 PRE_HEAP = -1, ///< = -1. |
|
78 POST_HEAP = -2 ///< = -2. |
|
79 }; |
73 |
80 |
74 private: |
81 private: |
75 class store; |
82 class store; |
76 |
83 |
77 std::vector<store> container; |
84 std::vector<store> _data; |
78 int minimum, head; |
85 int _min, _head; |
79 ItemIntMap &iimap; |
86 ItemIntMap &_iim; |
80 Compare comp; |
87 Compare _comp; |
81 int num_items; |
88 int _num_items; |
82 |
89 |
83 public: |
90 public: |
84 ///Status of the nodes |
91 /// \brief Constructor. |
85 enum State { |
92 /// |
86 ///The node is in the heap |
93 /// Constructor. |
87 IN_HEAP = 0, |
94 /// \param map A map that assigns \c int values to the items. |
88 ///The node has never been in the heap |
95 /// It is used internally to handle the cross references. |
89 PRE_HEAP = -1, |
96 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
90 ///The node was in the heap but it got out of it |
97 explicit BinomHeap(ItemIntMap &map) |
91 POST_HEAP = -2 |
98 : _min(0), _head(-1), _iim(map), _num_items(0) {} |
92 }; |
99 |
93 |
100 /// \brief Constructor. |
94 /// \brief The constructor |
101 /// |
95 /// |
102 /// Constructor. |
96 /// \c _iimap should be given to the constructor, since it is |
103 /// \param map A map that assigns \c int values to the items. |
97 /// used internally to handle the cross references. |
104 /// It is used internally to handle the cross references. |
98 explicit BinomHeap(ItemIntMap &_iimap) |
105 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. |
99 : minimum(0), head(-1), iimap(_iimap), num_items() {} |
106 /// \param comp The function object used for comparing the priorities. |
100 |
107 BinomHeap(ItemIntMap &map, const Compare &comp) |
101 /// \brief The constructor |
108 : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {} |
102 /// |
|
103 /// \c _iimap should be given to the constructor, since it is used |
|
104 /// internally to handle the cross references. \c _comp is an |
|
105 /// object for ordering of the priorities. |
|
106 BinomHeap(ItemIntMap &_iimap, const Compare &_comp) |
|
107 : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {} |
|
108 |
109 |
109 /// \brief The number of items stored in the heap. |
110 /// \brief The number of items stored in the heap. |
110 /// |
111 /// |
111 /// Returns the number of items stored in the heap. |
112 /// This function returns the number of items stored in the heap. |
112 int size() const { return num_items; } |
113 int size() const { return _num_items; } |
113 |
114 |
114 /// \brief Checks if the heap stores no items. |
115 /// \brief Check if the heap is empty. |
115 /// |
116 /// |
116 /// Returns \c true if and only if the heap stores no items. |
117 /// This function returns \c true if the heap is empty. |
117 bool empty() const { return num_items==0; } |
118 bool empty() const { return _num_items==0; } |
118 |
119 |
119 /// \brief Make empty this heap. |
120 /// \brief Make the heap empty. |
120 /// |
121 /// |
121 /// Make empty this heap. It does not change the cross reference |
122 /// This functon makes the heap empty. |
122 /// map. If you want to reuse a heap what is not surely empty you |
123 /// It does not change the cross reference map. If you want to reuse |
123 /// should first clear the heap and after that you should set the |
124 /// a heap that is not surely empty, you should first clear it and |
124 /// cross reference map for each item to \c PRE_HEAP. |
125 /// then you should set the cross reference map to \c PRE_HEAP |
|
126 /// for each item. |
125 void clear() { |
127 void clear() { |
126 container.clear(); minimum=0; num_items=0; head=-1; |
128 _data.clear(); _min=0; _num_items=0; _head=-1; |
127 } |
129 } |
128 |
130 |
129 /// \brief \c item gets to the heap with priority \c value independently |
131 /// \brief Set the priority of an item or insert it, if it is |
130 /// if \c item was already there. |
132 /// not stored in the heap. |
131 /// |
133 /// |
132 /// This method calls \ref push(\c item, \c value) if \c item is not |
134 /// This method sets the priority of the given item if it is |
133 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
135 /// already stored in the heap. Otherwise it inserts the given |
134 /// \ref increase(\c item, \c value) otherwise. |
136 /// item into the heap with the given priority. |
|
137 /// \param item The item. |
|
138 /// \param value The priority. |
135 void set (const Item& item, const Prio& value) { |
139 void set (const Item& item, const Prio& value) { |
136 int i=iimap[item]; |
140 int i=_iim[item]; |
137 if ( i >= 0 && container[i].in ) { |
141 if ( i >= 0 && _data[i].in ) { |
138 if ( comp(value, container[i].prio) ) decrease(item, value); |
142 if ( _comp(value, _data[i].prio) ) decrease(item, value); |
139 if ( comp(container[i].prio, value) ) increase(item, value); |
143 if ( _comp(_data[i].prio, value) ) increase(item, value); |
140 } else push(item, value); |
144 } else push(item, value); |
141 } |
145 } |
142 |
146 |
143 /// \brief Adds \c item to the heap with priority \c value. |
147 /// \brief Insert an item into the heap with the given priority. |
144 /// |
148 /// |
145 /// Adds \c item to the heap with priority \c value. |
149 /// This function inserts the given item into the heap with the |
146 /// \pre \c item must not be stored in the heap. |
150 /// given priority. |
|
151 /// \param item The item to insert. |
|
152 /// \param value The priority of the item. |
|
153 /// \pre \e item must not be stored in the heap. |
147 void push (const Item& item, const Prio& value) { |
154 void push (const Item& item, const Prio& value) { |
148 int i=iimap[item]; |
155 int i=_iim[item]; |
149 if ( i<0 ) { |
156 if ( i<0 ) { |
150 int s=container.size(); |
157 int s=_data.size(); |
151 iimap.set( item,s ); |
158 _iim.set( item,s ); |
152 store st; |
159 store st; |
153 st.name=item; |
160 st.name=item; |
154 container.push_back(st); |
161 _data.push_back(st); |
155 i=s; |
162 i=s; |
156 } |
163 } |
157 else { |
164 else { |
158 container[i].parent=container[i].right_neighbor=container[i].child=-1; |
165 _data[i].parent=_data[i].right_neighbor=_data[i].child=-1; |
159 container[i].degree=0; |
166 _data[i].degree=0; |
160 container[i].in=true; |
167 _data[i].in=true; |
161 } |
168 } |
162 container[i].prio=value; |
169 _data[i].prio=value; |
163 |
170 |
164 if( 0==num_items ) { head=i; minimum=i; } |
171 if( 0==_num_items ) { _head=i; _min=i; } |
165 else { merge(i); } |
172 else { merge(i); } |
166 |
173 |
167 minimum = find_min(); |
174 _min = findMin(); |
168 |
175 |
169 ++num_items; |
176 ++_num_items; |
170 } |
177 } |
171 |
178 |
172 /// \brief Returns the item with minimum priority relative to \c Compare. |
179 /// \brief Return the item having minimum priority. |
173 /// |
180 /// |
174 /// This method returns the item with minimum priority relative to \c |
181 /// This function returns the item having minimum priority. |
175 /// Compare. |
182 /// \pre The heap must be non-empty. |
176 /// \pre The heap must be nonempty. |
183 Item top() const { return _data[_min].name; } |
177 Item top() const { return container[minimum].name; } |
184 |
178 |
185 /// \brief The minimum priority. |
179 /// \brief Returns the minimum priority relative to \c Compare. |
186 /// |
180 /// |
187 /// This function returns the minimum priority. |
181 /// It returns the minimum priority relative to \c Compare. |
188 /// \pre The heap must be non-empty. |
182 /// \pre The heap must be nonempty. |
189 Prio prio() const { return _data[_min].prio; } |
183 const Prio& prio() const { return container[minimum].prio; } |
190 |
184 |
191 /// \brief The priority of the given item. |
185 /// \brief Returns the priority of \c item. |
192 /// |
186 /// |
193 /// This function returns the priority of the given item. |
187 /// It returns the priority of \c item. |
194 /// \param item The item. |
188 /// \pre \c item must be in the heap. |
195 /// \pre \e item must be in the heap. |
189 const Prio& operator[](const Item& item) const { |
196 const Prio& operator[](const Item& item) const { |
190 return container[iimap[item]].prio; |
197 return _data[_iim[item]].prio; |
191 } |
198 } |
192 |
199 |
193 /// \brief Deletes the item with minimum priority relative to \c Compare. |
200 /// \brief Remove the item having minimum priority. |
194 /// |
201 /// |
195 /// This method deletes the item with minimum priority relative to \c |
202 /// This function removes the item having minimum priority. |
196 /// Compare from the heap. |
|
197 /// \pre The heap must be non-empty. |
203 /// \pre The heap must be non-empty. |
198 void pop() { |
204 void pop() { |
199 container[minimum].in=false; |
205 _data[_min].in=false; |
200 |
206 |
201 int head_child=-1; |
207 int head_child=-1; |
202 if ( container[minimum].child!=-1 ) { |
208 if ( _data[_min].child!=-1 ) { |
203 int child=container[minimum].child; |
209 int child=_data[_min].child; |
204 int neighb; |
210 int neighb; |
205 int prev=-1; |
211 int prev=-1; |
206 while( child!=-1 ) { |
212 while( child!=-1 ) { |
207 neighb=container[child].right_neighbor; |
213 neighb=_data[child].right_neighbor; |
208 container[child].parent=-1; |
214 _data[child].parent=-1; |
209 container[child].right_neighbor=prev; |
215 _data[child].right_neighbor=prev; |
210 head_child=child; |
216 head_child=child; |
211 prev=child; |
217 prev=child; |
212 child=neighb; |
218 child=neighb; |
213 } |
219 } |
214 } |
220 } |
215 |
221 |
216 // The first case is that there are only one root. |
222 // The first case is that there are only one root. |
217 if ( -1==container[head].right_neighbor ) { |
223 if ( -1==_data[_head].right_neighbor ) { |
218 head=head_child; |
224 _head=head_child; |
219 } |
225 } |
220 // The case where there are more roots. |
226 // The case where there are more roots. |
221 else { |
227 else { |
222 if( head!=minimum ) { unlace(minimum); } |
228 if( _head!=_min ) { unlace(_min); } |
223 else { head=container[head].right_neighbor; } |
229 else { _head=_data[_head].right_neighbor; } |
224 |
230 |
225 merge(head_child); |
231 merge(head_child); |
226 } |
232 } |
227 minimum=find_min(); |
233 _min=findMin(); |
228 --num_items; |
234 --_num_items; |
229 } |
235 } |
230 |
236 |
231 /// \brief Deletes \c item from the heap. |
237 /// \brief Remove the given item from the heap. |
232 /// |
238 /// |
233 /// This method deletes \c item from the heap, if \c item was already |
239 /// This function removes the given item from the heap if it is |
234 /// stored in the heap. It is quite inefficient in Binomial heaps. |
240 /// already stored. |
|
241 /// \param item The item to delete. |
|
242 /// \pre \e item must be in the heap. |
235 void erase (const Item& item) { |
243 void erase (const Item& item) { |
236 int i=iimap[item]; |
244 int i=_iim[item]; |
237 if ( i >= 0 && container[i].in ) { |
245 if ( i >= 0 && _data[i].in ) { |
238 decrease( item, container[minimum].prio-1 ); |
246 decrease( item, _data[_min].prio-1 ); |
239 pop(); |
247 pop(); |
240 } |
248 } |
241 } |
249 } |
242 |
250 |
243 /// \brief Decreases the priority of \c item to \c value. |
251 /// \brief Decrease the priority of an item to the given value. |
244 /// |
252 /// |
245 /// This method decreases the priority of \c item to \c value. |
253 /// This function decreases the priority of an item to the given value. |
246 /// \pre \c item must be stored in the heap with priority at least \c |
254 /// \param item The item. |
247 /// value relative to \c Compare. |
255 /// \param value The priority. |
|
256 /// \pre \e item must be stored in the heap with priority at least \e value. |
248 void decrease (Item item, const Prio& value) { |
257 void decrease (Item item, const Prio& value) { |
249 int i=iimap[item]; |
258 int i=_iim[item]; |
250 |
259 |
251 if( comp( value,container[i].prio ) ) { |
260 if( _comp( value,_data[i].prio ) ) { |
252 container[i].prio=value; |
261 _data[i].prio=value; |
253 |
262 |
254 int p_loc=container[i].parent, loc=i; |
263 int p_loc=_data[i].parent, loc=i; |
255 int parent, child, neighb; |
264 int parent, child, neighb; |
256 |
265 |
257 while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) { |
266 while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) { |
258 |
267 |
259 // parent set for other loc_child |
268 // parent set for other loc_child |
260 child=container[loc].child; |
269 child=_data[loc].child; |
261 while( -1!=child ) { |
270 while( -1!=child ) { |
262 container[child].parent=p_loc; |
271 _data[child].parent=p_loc; |
263 child=container[child].right_neighbor; |
272 child=_data[child].right_neighbor; |
264 } |
273 } |
265 |
274 |
266 // parent set for other p_loc_child |
275 // parent set for other p_loc_child |
267 child=container[p_loc].child; |
276 child=_data[p_loc].child; |
268 while( -1!=child ) { |
277 while( -1!=child ) { |
269 container[child].parent=loc; |
278 _data[child].parent=loc; |
270 child=container[child].right_neighbor; |
279 child=_data[child].right_neighbor; |
271 } |
280 } |
272 |
281 |
273 child=container[p_loc].child; |
282 child=_data[p_loc].child; |
274 container[p_loc].child=container[loc].child; |
283 _data[p_loc].child=_data[loc].child; |
275 if( child==loc ) |
284 if( child==loc ) |
276 child=p_loc; |
285 child=p_loc; |
277 container[loc].child=child; |
286 _data[loc].child=child; |
278 |
287 |
279 // left_neighb set for p_loc |
288 // left_neighb set for p_loc |
280 if( container[loc].child!=p_loc ) { |
289 if( _data[loc].child!=p_loc ) { |
281 while( container[child].right_neighbor!=loc ) |
290 while( _data[child].right_neighbor!=loc ) |
282 child=container[child].right_neighbor; |
291 child=_data[child].right_neighbor; |
283 container[child].right_neighbor=p_loc; |
292 _data[child].right_neighbor=p_loc; |
284 } |
293 } |
285 |
294 |
286 // left_neighb set for loc |
295 // left_neighb set for loc |
287 parent=container[p_loc].parent; |
296 parent=_data[p_loc].parent; |
288 if( -1!=parent ) child=container[parent].child; |
297 if( -1!=parent ) child=_data[parent].child; |
289 else child=head; |
298 else child=_head; |
290 |
299 |
291 if( child!=p_loc ) { |
300 if( child!=p_loc ) { |
292 while( container[child].right_neighbor!=p_loc ) |
301 while( _data[child].right_neighbor!=p_loc ) |
293 child=container[child].right_neighbor; |
302 child=_data[child].right_neighbor; |
294 container[child].right_neighbor=loc; |
303 _data[child].right_neighbor=loc; |
295 } |
304 } |
296 |
305 |
297 neighb=container[p_loc].right_neighbor; |
306 neighb=_data[p_loc].right_neighbor; |
298 container[p_loc].right_neighbor=container[loc].right_neighbor; |
307 _data[p_loc].right_neighbor=_data[loc].right_neighbor; |
299 container[loc].right_neighbor=neighb; |
308 _data[loc].right_neighbor=neighb; |
300 |
309 |
301 container[p_loc].parent=loc; |
310 _data[p_loc].parent=loc; |
302 container[loc].parent=parent; |
311 _data[loc].parent=parent; |
303 |
312 |
304 if( -1!=parent && container[parent].child==p_loc ) |
313 if( -1!=parent && _data[parent].child==p_loc ) |
305 container[parent].child=loc; |
314 _data[parent].child=loc; |
306 |
315 |
307 /*if new parent will be the first root*/ |
316 /*if new parent will be the first root*/ |
308 if( head==p_loc ) |
317 if( _head==p_loc ) |
309 head=loc; |
318 _head=loc; |
310 |
319 |
311 p_loc=container[loc].parent; |
320 p_loc=_data[loc].parent; |
312 } |
321 } |
313 } |
322 } |
314 if( comp(value,container[minimum].prio) ) { |
323 if( _comp(value,_data[_min].prio) ) { |
315 minimum=i; |
324 _min=i; |
316 } |
325 } |
317 } |
326 } |
318 |
327 |
319 /// \brief Increases the priority of \c item to \c value. |
328 /// \brief Increase the priority of an item to the given value. |
320 /// |
329 /// |
321 /// This method sets the priority of \c item to \c value. Though |
330 /// This function increases the priority of an item to the given value. |
322 /// there is no precondition on the priority of \c item, this |
331 /// \param item The item. |
323 /// method should be used only if it is indeed necessary to increase |
332 /// \param value The priority. |
324 /// (relative to \c Compare) the priority of \c item, because this |
333 /// \pre \e item must be stored in the heap with priority at most \e value. |
325 /// method is inefficient. |
|
326 void increase (Item item, const Prio& value) { |
334 void increase (Item item, const Prio& value) { |
327 erase(item); |
335 erase(item); |
328 push(item, value); |
336 push(item, value); |
329 } |
337 } |
330 |
338 |
331 |
339 /// \brief Return the state of an item. |
332 /// \brief Returns if \c item is in, has already been in, or has never |
340 /// |
333 /// been in the heap. |
341 /// This method returns \c PRE_HEAP if the given item has never |
334 /// |
342 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
335 /// This method returns PRE_HEAP if \c item has never been in the |
343 /// and \c POST_HEAP otherwise. |
336 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
344 /// In the latter case it is possible that the item will get back |
337 /// otherwise. In the latter case it is possible that \c item will |
345 /// to the heap again. |
338 /// get back to the heap again. |
346 /// \param item The item. |
339 State state(const Item &item) const { |
347 State state(const Item &item) const { |
340 int i=iimap[item]; |
348 int i=_iim[item]; |
341 if( i>=0 ) { |
349 if( i>=0 ) { |
342 if ( container[i].in ) i=0; |
350 if ( _data[i].in ) i=0; |
343 else i=-2; |
351 else i=-2; |
344 } |
352 } |
345 return State(i); |
353 return State(i); |
346 } |
354 } |
347 |
355 |
348 /// \brief Sets the state of the \c item in the heap. |
356 /// \brief Set the state of an item in the heap. |
349 /// |
357 /// |
350 /// Sets the state of the \c item in the heap. It can be used to |
358 /// This function sets the state of the given item in the heap. |
351 /// manually clear the heap when it is important to achive the |
359 /// It can be used to manually clear the heap when it is important |
352 /// better time complexity. |
360 /// to achive better time complexity. |
353 /// \param i The item. |
361 /// \param i The item. |
354 /// \param st The state. It should not be \c IN_HEAP. |
362 /// \param st The state. It should not be \c IN_HEAP. |
355 void state(const Item& i, State st) { |
363 void state(const Item& i, State st) { |
356 switch (st) { |
364 switch (st) { |
357 case POST_HEAP: |
365 case POST_HEAP: |
358 case PRE_HEAP: |
366 case PRE_HEAP: |
359 if (state(i) == IN_HEAP) { |
367 if (state(i) == IN_HEAP) { |
360 erase(i); |
368 erase(i); |
361 } |
369 } |
362 iimap[i] = st; |
370 _iim[i] = st; |
363 break; |
371 break; |
364 case IN_HEAP: |
372 case IN_HEAP: |
365 break; |
373 break; |
366 } |
374 } |
367 } |
375 } |
368 |
376 |
369 private: |
377 private: |
370 int find_min() { |
378 int findMin() { |
371 int min_loc=-1, min_val; |
379 int min_loc=-1, min_val; |
372 int x=head; |
380 int x=_head; |
373 if( x!=-1 ) { |
381 if( x!=-1 ) { |
374 min_val=container[x].prio; |
382 min_val=_data[x].prio; |
375 min_loc=x; |
383 min_loc=x; |
376 x=container[x].right_neighbor; |
384 x=_data[x].right_neighbor; |
377 |
385 |
378 while( x!=-1 ) { |
386 while( x!=-1 ) { |
379 if( comp( container[x].prio,min_val ) ) { |
387 if( _comp( _data[x].prio,min_val ) ) { |
380 min_val=container[x].prio; |
388 min_val=_data[x].prio; |
381 min_loc=x; |
389 min_loc=x; |
382 } |
390 } |
383 x=container[x].right_neighbor; |
391 x=_data[x].right_neighbor; |
384 } |
392 } |
385 } |
393 } |
386 return min_loc; |
394 return min_loc; |
387 } |
395 } |
388 |
396 |
389 void merge(int a) { |
397 void merge(int a) { |
390 interleave(a); |
398 interleave(a); |
391 |
399 |
392 int x=head; |
400 int x=_head; |
393 if( -1!=x ) { |
401 if( -1!=x ) { |
394 int x_prev=-1, x_next=container[x].right_neighbor; |
402 int x_prev=-1, x_next=_data[x].right_neighbor; |
395 while( -1!=x_next ) { |
403 while( -1!=x_next ) { |
396 if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) { |
404 if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { |
397 x_prev=x; |
405 x_prev=x; |
398 x=x_next; |
406 x=x_next; |
399 } |
407 } |
400 else { |
408 else { |
401 if( comp(container[x].prio,container[x_next].prio) ) { |
409 if( _comp(_data[x].prio,_data[x_next].prio) ) { |
402 container[x].right_neighbor=container[x_next].right_neighbor; |
410 _data[x].right_neighbor=_data[x_next].right_neighbor; |
403 fuse(x_next,x); |
411 fuse(x_next,x); |
404 } |
412 } |
405 else { |
413 else { |
406 if( -1==x_prev ) { head=x_next; } |
414 if( -1==x_prev ) { _head=x_next; } |
407 else { |
415 else { |
408 container[x_prev].right_neighbor=x_next; |
416 _data[x_prev].right_neighbor=x_next; |
409 } |
417 } |
410 fuse(x,x_next); |
418 fuse(x,x_next); |
411 x=x_next; |
419 x=x_next; |
412 } |
420 } |
413 } |
421 } |
414 x_next=container[x].right_neighbor; |
422 x_next=_data[x].right_neighbor; |
415 } |
423 } |
416 } |
424 } |
417 } |
425 } |
418 |
426 |
419 void interleave(int a) { |
427 void interleave(int a) { |
420 int other=-1, head_other=-1; |
428 int other=-1, head_other=-1; |
421 |
429 |
422 while( -1!=a || -1!=head ) { |
430 while( -1!=a || -1!=_head ) { |
423 if( -1==a ) { |
431 if( -1==a ) { |
424 if( -1==head_other ) { |
432 if( -1==head_other ) { |
425 head_other=head; |
433 head_other=_head; |
426 } |
434 } |
427 else { |
435 else { |
428 container[other].right_neighbor=head; |
436 _data[other].right_neighbor=_head; |
429 } |
437 } |
430 head=-1; |
438 _head=-1; |
431 } |
439 } |
432 else if( -1==head ) { |
440 else if( -1==_head ) { |
433 if( -1==head_other ) { |
441 if( -1==head_other ) { |
434 head_other=a; |
442 head_other=a; |
435 } |
443 } |
436 else { |
444 else { |
437 container[other].right_neighbor=a; |
445 _data[other].right_neighbor=a; |
438 } |
446 } |
439 a=-1; |
447 a=-1; |
440 } |
448 } |
441 else { |
449 else { |
442 if( container[a].degree<container[head].degree ) { |
450 if( _data[a].degree<_data[_head].degree ) { |
443 if( -1==head_other ) { |
451 if( -1==head_other ) { |
444 head_other=a; |
452 head_other=a; |
445 } |
453 } |
446 else { |
454 else { |
447 container[other].right_neighbor=a; |
455 _data[other].right_neighbor=a; |
448 } |
456 } |
449 other=a; |
457 other=a; |
450 a=container[a].right_neighbor; |
458 a=_data[a].right_neighbor; |
451 } |
459 } |
452 else { |
460 else { |
453 if( -1==head_other ) { |
461 if( -1==head_other ) { |
454 head_other=head; |
462 head_other=_head; |
455 } |
463 } |
456 else { |
464 else { |
457 container[other].right_neighbor=head; |
465 _data[other].right_neighbor=_head; |
458 } |
466 } |
459 other=head; |
467 other=_head; |
460 head=container[head].right_neighbor; |
468 _head=_data[_head].right_neighbor; |
461 } |
469 } |
462 } |
470 } |
463 } |
471 } |
464 head=head_other; |
472 _head=head_other; |
465 } |
473 } |
466 |
474 |
467 // Lacing a under b |
475 // Lacing a under b |
468 void fuse(int a, int b) { |
476 void fuse(int a, int b) { |
469 container[a].parent=b; |
477 _data[a].parent=b; |
470 container[a].right_neighbor=container[b].child; |
478 _data[a].right_neighbor=_data[b].child; |
471 container[b].child=a; |
479 _data[b].child=a; |
472 |
480 |
473 ++container[b].degree; |
481 ++_data[b].degree; |
474 } |
482 } |
475 |
483 |
476 // It is invoked only if a has siblings. |
484 // It is invoked only if a has siblings. |
477 void unlace(int a) { |
485 void unlace(int a) { |
478 int neighb=container[a].right_neighbor; |
486 int neighb=_data[a].right_neighbor; |
479 int other=head; |
487 int other=_head; |
480 |
488 |
481 while( container[other].right_neighbor!=a ) |
489 while( _data[other].right_neighbor!=a ) |
482 other=container[other].right_neighbor; |
490 other=_data[other].right_neighbor; |
483 container[other].right_neighbor=neighb; |
491 _data[other].right_neighbor=neighb; |
484 } |
492 } |
485 |
493 |
486 private: |
494 private: |
487 |
495 |
488 class store { |
496 class store { |