3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_PAIRING_HEAP_H
20 #define LEMON_PAIRING_HEAP_H
24 ///\brief Pairing Heap implementation.
28 #include <lemon/math.h>
34 ///\brief Pairing Heap.
36 ///This class implements the \e Pairing \e heap data structure. A \e heap
37 ///is a data structure for storing items with specified values called \e
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.
42 ///The methods \ref increase and \ref erase are not efficient in a Pairing
43 ///heap. In case of many calls to these operations, it is better to use a
44 ///\ref BinHeap "binary heap".
46 ///\param _Prio Type of the priority of the items.
47 ///\param _ItemIntMap A read and writable Item int map, used internally
48 ///to handle the cross references.
49 ///\param _Compare A class for the ordering of the priorities. The
50 ///default is \c std::less<_Prio>.
54 ///\author Dorian Batha
57 template <typename _Prio,
61 template <typename _Prio,
63 typename _Compare = std::less<_Prio> >
67 typedef _ItemIntMap ItemIntMap;
69 typedef typename ItemIntMap::Key Item;
70 typedef std::pair<Item,Prio> Pair;
71 typedef _Compare Compare;
76 std::vector<store> container;
83 ///Status of the nodes
85 ///The node is in the heap
87 ///The node has never been in the heap
89 ///The node was in the heap but it got out of it
93 /// \brief The constructor
95 /// \c _iimap should be given to the constructor, since it is
96 /// used internally to handle the cross references.
97 explicit PairingHeap(ItemIntMap &_iimap)
98 : minimum(0), iimap(_iimap), num_items(0) {}
100 /// \brief The constructor
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) {}
108 /// \brief The number of items stored in the heap.
110 /// Returns the number of items stored in the heap.
111 int size() const { return num_items; }
113 /// \brief Checks if the heap stores no items.
115 /// Returns \c true if and only if the heap stores no items.
116 bool empty() const { return num_items==0; }
118 /// \brief Make empty this heap.
120 /// Make empty this heap. It does not change the cross reference
121 /// map. If you want to reuse a heap what is not surely empty you
122 /// should first clear the heap and after that you should set the
123 /// cross reference map for each item to \c PRE_HEAP.
130 /// \brief \c item gets to the heap with priority \c value independently
131 /// if \c item was already there.
133 /// This method calls \ref push(\c item, \c value) if \c item is not
134 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
135 /// \ref increase(\c item, \c value) otherwise.
136 void set (const Item& item, const Prio& value) {
138 if ( i>=0 && container[i].in ) {
139 if ( comp(value, container[i].prio) ) decrease(item, value);
140 if ( comp(container[i].prio, value) ) increase(item, value);
141 } else push(item, value);
144 /// \brief Adds \c item to the heap with priority \c value.
146 /// Adds \c item to the heap with priority \c value.
147 /// \pre \c item must not be stored in the heap.
148 void push (const Item& item, const Prio& value) {
151 int s=container.size();
155 container.push_back(st);
158 container[i].parent=container[i].child=-1;
159 container[i].left_child=false;
160 container[i].degree=0;
161 container[i].in=true;
164 container[i].prio=value;
166 if ( num_items!=0 ) {
167 if ( comp( value, container[minimum].prio) ) {
171 else fuse(minimum,i);
178 /// \brief Returns the item with minimum priority relative to \c Compare.
180 /// This method returns the item with minimum priority relative to \c
182 /// \pre The heap must be nonempty.
183 Item top() const { return container[minimum].name; }
185 /// \brief Returns the minimum priority relative to \c Compare.
187 /// It returns the minimum priority relative to \c Compare.
188 /// \pre The heap must be nonempty.
189 const Prio& prio() const { return container[minimum].prio; }
191 /// \brief Returns the priority of \c item.
193 /// It returns the priority of \c item.
194 /// \pre \c item must be in the heap.
195 const Prio& operator[](const Item& item) const {
196 return container[iimap[item]].prio;
199 /// \brief Deletes the item with minimum priority relative to \c Compare.
201 /// This method deletes the item with minimum priority relative to \c
202 /// Compare from the heap.
203 /// \pre The heap must be non-empty.
205 int TreeArray[num_items];
206 int i=0, num_child=0, child_right = 0;
207 container[minimum].in=false;
209 if( -1!=container[minimum].child ) {
210 i=container[minimum].child;
211 TreeArray[num_child] = i;
212 container[i].parent = -1;
213 container[minimum].child = -1;
217 while( container[i].child!=-1 ) {
218 ch=container[i].child;
219 if( container[ch].left_child && i==container[ch].parent ) {
223 if( container[ch].left_child ) {
224 child_right=container[ch].parent;
225 container[ch].parent = i;
226 --container[i].degree;
230 container[i].child=-1;
231 container[i].degree=0;
233 container[child_right].parent = -1;
234 TreeArray[num_child] = child_right;
241 for( i=0; i<num_child-1; i+=2 ) {
242 if ( !comp(container[TreeArray[i]].prio,
243 container[TreeArray[i+1]].prio) ) {
245 TreeArray[i]=TreeArray[i+1];
246 TreeArray[i+1]=other;
248 fuse( TreeArray[i], TreeArray[i+1] );
251 i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
253 if ( comp(container[TreeArray[i]].prio,
254 container[TreeArray[i-2]].prio) ) {
256 TreeArray[i]=TreeArray[i-2];
257 TreeArray[i-2]=other;
259 fuse( TreeArray[i-2], TreeArray[i] );
262 minimum = TreeArray[0];
265 if ( 0==num_child ) {
266 minimum = container[minimum].child;
269 if (minimum >= 0) container[minimum].left_child = false;
274 /// \brief Deletes \c item from the heap.
276 /// This method deletes \c item from the heap, if \c item was already
277 /// stored in the heap. It is quite inefficient in Pairing heaps.
278 void erase (const Item& item) {
280 if ( i>=0 && container[i].in ) {
281 decrease( item, container[minimum].prio-1 );
286 /// \brief Decreases the priority of \c item to \c value.
288 /// This method decreases the priority of \c item to \c value.
289 /// \pre \c item must be stored in the heap with priority at least \c
290 /// value relative to \c Compare.
291 void decrease (Item item, const Prio& value) {
293 container[i].prio=value;
294 int p=container[i].parent;
296 if( container[i].left_child && i!=container[p].child ) {
297 p=container[p].parent;
300 if ( p!=-1 && comp(value,container[p].prio) ) {
302 if ( comp(container[minimum].prio,value) ) {
311 /// \brief Increases the priority of \c item to \c value.
313 /// This method sets the priority of \c item to \c value. Though
314 /// there is no precondition on the priority of \c item, this
315 /// method should be used only if it is indeed necessary to increase
316 /// (relative to \c Compare) the priority of \c item, because this
317 /// method is inefficient.
318 void increase (Item item, const Prio& value) {
323 /// \brief Returns if \c item is in, has already been in, or has never
324 /// been in the heap.
326 /// This method returns PRE_HEAP if \c item has never been in the
327 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
328 /// otherwise. In the latter case it is possible that \c item will
329 /// get back to the heap again.
330 State state(const Item &item) const {
333 if( container[i].in ) i=0;
339 /// \brief Sets the state of the \c item in the heap.
341 /// Sets the state of the \c item in the heap. It can be used to
342 /// manually clear the heap when it is important to achive the
343 /// better time complexity.
344 /// \param i The item.
345 /// \param st The state. It should not be \c IN_HEAP.
346 void state(const Item& i, State st) {
350 if (state(i) == IN_HEAP) erase(i);
360 void cut(int a, int b) {
362 switch (container[a].degree) {
364 child_a = container[container[a].child].parent;
365 if( container[a].left_child ) {
366 container[child_a].left_child=true;
367 container[b].child=child_a;
368 container[child_a].parent=container[a].parent;
371 container[child_a].left_child=false;
372 container[child_a].parent=b;
373 if( a!=container[b].child )
374 container[container[b].child].parent=child_a;
376 container[b].child=child_a;
378 --container[a].degree;
379 container[container[a].child].parent=a;
383 child_a = container[a].child;
384 if( !container[child_a].left_child ) {
385 --container[a].degree;
386 if( container[a].left_child ) {
387 container[child_a].left_child=true;
388 container[child_a].parent=container[a].parent;
389 container[b].child=child_a;
392 container[child_a].left_child=false;
393 container[child_a].parent=b;
394 if( a!=container[b].child )
395 container[container[b].child].parent=child_a;
397 container[b].child=child_a;
399 container[a].child=-1;
402 --container[b].degree;
403 if( container[a].left_child ) {
405 (1==container[b].degree) ? container[a].parent : -1;
407 if (1==container[b].degree)
408 container[container[b].child].parent=b;
410 container[b].child=-1;
416 --container[b].degree;
417 if( container[a].left_child ) {
419 (0!=container[b].degree) ? container[a].parent : -1;
421 if( 0!=container[b].degree )
422 container[container[b].child].parent=b;
424 container[b].child=-1;
428 container[a].parent=-1;
429 container[a].left_child=false;
432 void fuse(int a, int b) {
433 int child_a = container[a].child;
434 int child_b = container[b].child;
435 container[a].child=b;
436 container[b].parent=a;
437 container[b].left_child=true;
440 container[b].child=child_a;
441 container[child_a].parent=b;
442 container[child_a].left_child=false;
443 ++container[b].degree;
446 container[b].child=child_b;
447 container[child_b].parent=child_a;
450 else { ++container[a].degree; }
454 friend class PairingHeap;
464 store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
470 #endif //LEMON_PAIRING_HEAP_H