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