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