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