COIN-OR::LEMON - Graph Library

source: lemon/lemon/pairing_heap.h @ 749:bdc7dfc8c054

Last change on this file since 749:bdc7dfc8c054 was 749:bdc7dfc8c054, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Bug fix in PairingHeap::pop() (#301)

File size: 14.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_PAIRING_HEAP_H
20#define LEMON_PAIRING_HEAP_H
21
22///\file
23///\ingroup auxdat
24///\brief Pairing Heap implementation.
25
26#include <vector>
27#include <functional>
28#include <lemon/math.h>
29
30namespace lemon {
31
32  /// \ingroup auxdat
33  ///
34  ///\brief Pairing Heap.
35  ///
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.
41  ///
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".
45  ///
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>.
51  ///
52  ///\sa BinHeap
53  ///\sa Dijkstra
54  ///\author Dorian Batha
55
56#ifdef DOXYGEN
57  template <typename _Prio,
58            typename _ItemIntMap,
59            typename _Compare>
60#else
61  template <typename _Prio,
62            typename _ItemIntMap,
63            typename _Compare = std::less<_Prio> >
64#endif
65  class PairingHeap {
66  public:
67    typedef _ItemIntMap ItemIntMap;
68    typedef _Prio Prio;
69    typedef typename ItemIntMap::Key Item;
70    typedef std::pair<Item,Prio> Pair;
71    typedef _Compare Compare;
72
73  private:
74    class store;
75
76    std::vector<store> container;
77    int minimum;
78    ItemIntMap &iimap;
79    Compare comp;
80    int num_items;
81
82  public:
83    ///Status of the nodes
84    enum State {
85      ///The node is in the heap
86      IN_HEAP = 0,
87      ///The node has never been in the heap
88      PRE_HEAP = -1,
89      ///The node was in the heap but it got out of it
90      POST_HEAP = -2
91    };
92
93    /// \brief The constructor
94    ///
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) {}
99
100    /// \brief The constructor
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    /// \brief The number of items stored in the heap.
109    ///
110    /// Returns the number of items stored in the heap.
111    int size() const { return num_items; }
112
113    /// \brief Checks if the heap stores no items.
114    ///
115    ///   Returns \c true if and only if the heap stores no items.
116    bool empty() const { return num_items==0; }
117
118    /// \brief Make empty this heap.
119    ///
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.
124    void clear() {
125      container.clear();
126      minimum = 0;
127      num_items = 0;
128    }
129
130    /// \brief \c item gets to the heap with priority \c value independently
131    /// if \c item was already there.
132    ///
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) {
137      int i=iimap[item];
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);
142    }
143
144    /// \brief Adds \c item to the heap with priority \c value.
145    ///
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) {
149      int i=iimap[item];
150      if( i<0 ) {
151        int s=container.size();
152        iimap.set(item, s);
153        store st;
154        st.name=item;
155        container.push_back(st);
156        i=s;
157      } else {
158        container[i].parent=container[i].child=-1;
159        container[i].left_child=false;
160        container[i].degree=0;
161        container[i].in=true;
162      }
163
164      container[i].prio=value;
165
166      if ( num_items!=0 ) {
167        if ( comp( value, container[minimum].prio) ) {
168          fuse(i,minimum);
169          minimum=i;
170        }
171        else fuse(minimum,i);
172      }
173      else minimum=i;
174
175      ++num_items;
176    }
177
178    /// \brief Returns the item with minimum priority relative to \c Compare.
179    ///
180    /// This method returns the item with minimum priority relative to \c
181    /// Compare.
182    /// \pre The heap must be nonempty.
183    Item top() const { return container[minimum].name; }
184
185    /// \brief Returns the minimum priority relative to \c Compare.
186    ///
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; }
190
191    /// \brief Returns the priority of \c item.
192    ///
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;
197    }
198
199    /// \brief Deletes the item with minimum priority relative to \c Compare.
200    ///
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.
204    void pop() {
205      int TreeArray[num_items];
206      int i=0, num_child=0, child_right = 0;
207      container[minimum].in=false;
208
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;
214
215        ++num_child;
216        int ch=-1;
217        while( container[i].child!=-1 ) {
218          ch=container[i].child;
219          if( container[ch].left_child && i==container[ch].parent ) {
220            i=ch;
221            //break;
222          } else {
223            if( container[ch].left_child ) {
224              child_right=container[ch].parent;
225              container[ch].parent = i;
226              --container[i].degree;
227            }
228            else {
229              child_right=ch;
230              container[i].child=-1;
231              container[i].degree=0;
232            }
233            container[child_right].parent = -1;
234            TreeArray[num_child] = child_right;
235            i = child_right;
236            ++num_child;
237          }
238        }
239
240        int other;
241        for( i=0; i<num_child-1; i+=2 ) {
242          if ( !comp(container[TreeArray[i]].prio,
243                     container[TreeArray[i+1]].prio) ) {
244            other=TreeArray[i];
245            TreeArray[i]=TreeArray[i+1];
246            TreeArray[i+1]=other;
247          }
248          fuse( TreeArray[i], TreeArray[i+1] );
249        }
250
251        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
252        while(i>=2) {
253          if ( comp(container[TreeArray[i]].prio,
254                    container[TreeArray[i-2]].prio) ) {
255            other=TreeArray[i];
256            TreeArray[i]=TreeArray[i-2];
257            TreeArray[i-2]=other;
258          }
259          fuse( TreeArray[i-2], TreeArray[i] );
260          i-=2;
261        }
262        minimum = TreeArray[0];
263      }
264
265      if ( 0==num_child ) {
266        minimum = container[minimum].child;
267      }
268
269      if (minimum >= 0) container[minimum].left_child = false;
270
271      --num_items;
272    }
273
274    /// \brief Deletes \c item from the heap.
275    ///
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) {
279      int i=iimap[item];
280      if ( i>=0 && container[i].in ) {
281        decrease( item, container[minimum].prio-1 );
282        pop();
283      }
284    }
285
286    /// \brief Decreases the priority of \c item to \c value.
287    ///
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) {
292      int i=iimap[item];
293      container[i].prio=value;
294      int p=container[i].parent;
295
296      if( container[i].left_child && i!=container[p].child ) {
297        p=container[p].parent;
298      }
299
300      if ( p!=-1 && comp(value,container[p].prio) ) {
301        cut(i,p);
302        if ( comp(container[minimum].prio,value) ) {
303          fuse(minimum,i);
304        } else {
305          fuse(i,minimum);
306          minimum=i;
307        }
308      }
309    }
310
311    /// \brief Increases the priority of \c item to \c value.
312    ///
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) {
319      erase(item);
320      push(item,value);
321    }
322
323    /// \brief Returns if \c item is in, has already been in, or has never
324    /// been in the heap.
325    ///
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 {
331      int i=iimap[item];
332      if( i>=0 ) {
333        if( container[i].in ) i=0;
334        else i=-2;
335      }
336      return State(i);
337    }
338
339    /// \brief Sets the state of the \c item in the heap.
340    ///
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) {
347      switch (st) {
348      case POST_HEAP:
349      case PRE_HEAP:
350        if (state(i) == IN_HEAP) erase(i);
351        iimap[i]=st;
352        break;
353      case IN_HEAP:
354        break;
355      }
356    }
357
358  private:
359
360    void cut(int a, int b) {
361      int child_a;
362      switch (container[a].degree) {
363        case 2:
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;
369          }
370          else {
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;
375            else
376              container[b].child=child_a;
377          }
378          --container[a].degree;
379          container[container[a].child].parent=a;
380          break;
381
382        case 1:
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;
390            }
391            else {
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;
396              else
397                container[b].child=child_a;
398            }
399            container[a].child=-1;
400          }
401          else {
402            --container[b].degree;
403            if( container[a].left_child ) {
404              container[b].child =
405                (1==container[b].degree) ? container[a].parent : -1;
406            } else {
407              if (1==container[b].degree)
408                container[container[b].child].parent=b;
409              else
410                container[b].child=-1;
411            }
412          }
413          break;
414
415        case 0:
416          --container[b].degree;
417          if( container[a].left_child ) {
418            container[b].child =
419              (0!=container[b].degree) ? container[a].parent : -1;
420          } else {
421            if( 0!=container[b].degree )
422              container[container[b].child].parent=b;
423            else
424              container[b].child=-1;
425          }
426          break;
427      }
428      container[a].parent=-1;
429      container[a].left_child=false;
430    }
431
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;
438
439      if( -1!=child_a ) {
440        container[b].child=child_a;
441        container[child_a].parent=b;
442        container[child_a].left_child=false;
443        ++container[b].degree;
444
445        if( -1!=child_b ) {
446           container[b].child=child_b;
447           container[child_b].parent=child_a;
448        }
449      }
450      else { ++container[a].degree; }
451    }
452
453    class store {
454      friend class PairingHeap;
455
456      Item name;
457      int parent;
458      int child;
459      bool left_child;
460      int degree;
461      bool in;
462      Prio prio;
463
464      store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
465    };
466  };
467
468} //namespace lemon
469
470#endif //LEMON_PAIRING_HEAP_H
471
Note: See TracBrowser for help on using the repository browser.