COIN-OR::LEMON - Graph Library

source: lemon/lemon/pairing_heap.h @ 748:d1a9224f1e30

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

Add fourary, k-ary, pairing and binomial heaps (#301)
These structures were implemented by Dorian Batha.

File size: 13.9 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      --num_items;
270    }
271
272    /// \brief Deletes \c item from the heap.
273    ///
274    /// This method deletes \c item from the heap, if \c item was already
275    /// stored in the heap. It is quite inefficient in Pairing heaps.
276    void erase (const Item& item) {
277      int i=iimap[item];
278      if ( i>=0 && container[i].in ) {
279        decrease( item, container[minimum].prio-1 );
280        pop();
281      }
282    }
283
284    /// \brief Decreases the priority of \c item to \c value.
285    ///
286    /// This method decreases the priority of \c item to \c value.
287    /// \pre \c item must be stored in the heap with priority at least \c
288    ///   value relative to \c Compare.
289    void decrease (Item item, const Prio& value) {
290      int i=iimap[item];
291      container[i].prio=value;
292      int p=container[i].parent;
293
294      if( container[i].left_child && i!=container[p].child ) {
295        p=container[p].parent;
296      }
297
298      if ( p!=-1 && comp(value,container[p].prio) ) {
299        cut(i,p);
300        if ( comp(container[minimum].prio,value) ) {
301          fuse(minimum,i);
302        } else {
303          fuse(i,minimum);
304          minimum=i;
305        }
306      }
307    }
308
309    /// \brief Increases the priority of \c item to \c value.
310    ///
311    /// This method sets the priority of \c item to \c value. Though
312    /// there is no precondition on the priority of \c item, this
313    /// method should be used only if it is indeed necessary to increase
314    /// (relative to \c Compare) the priority of \c item, because this
315    /// method is inefficient.
316    void increase (Item item, const Prio& value) {
317      erase(item);
318      push(item,value);
319    }
320
321    /// \brief Returns if \c item is in, has already been in, or has never
322    /// been in the heap.
323    ///
324    /// This method returns PRE_HEAP if \c item has never been in the
325    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
326    /// otherwise. In the latter case it is possible that \c item will
327    /// get back to the heap again.
328    State state(const Item &item) const {
329      int i=iimap[item];
330      if( i>=0 ) {
331        if( container[i].in ) i=0;
332        else i=-2;
333      }
334      return State(i);
335    }
336
337    /// \brief Sets the state of the \c item in the heap.
338    ///
339    /// Sets the state of the \c item in the heap. It can be used to
340    /// manually clear the heap when it is important to achive the
341    /// better time complexity.
342    /// \param i The item.
343    /// \param st The state. It should not be \c IN_HEAP.
344    void state(const Item& i, State st) {
345      switch (st) {
346      case POST_HEAP:
347      case PRE_HEAP:
348        if (state(i) == IN_HEAP) erase(i);
349        iimap[i]=st;
350        break;
351      case IN_HEAP:
352        break;
353      }
354    }
355
356  private:
357
358    void cut(int a, int b) {
359      int child_a;
360      switch (container[a].degree) {
361        case 2:
362          child_a = container[container[a].child].parent;
363          if( container[a].left_child ) {
364            container[child_a].left_child=true;
365            container[b].child=child_a;
366            container[child_a].parent=container[a].parent;
367          }
368          else {
369            container[child_a].left_child=false;
370            container[child_a].parent=b;
371            if( a!=container[b].child )
372              container[container[b].child].parent=child_a;
373            else
374              container[b].child=child_a;
375          }
376          --container[a].degree;
377          container[container[a].child].parent=a;
378          break;
379
380        case 1:
381          child_a = container[a].child;
382          if( !container[child_a].left_child ) {
383            --container[a].degree;
384            if( container[a].left_child ) {
385              container[child_a].left_child=true;
386              container[child_a].parent=container[a].parent;
387              container[b].child=child_a;
388            }
389            else {
390              container[child_a].left_child=false;
391              container[child_a].parent=b;
392              if( a!=container[b].child )
393                container[container[b].child].parent=child_a;
394              else
395                container[b].child=child_a;
396            }
397            container[a].child=-1;
398          }
399          else {
400            --container[b].degree;
401            if( container[a].left_child ) {
402              container[b].child =
403                (1==container[b].degree) ? container[a].parent : -1;
404            } else {
405              if (1==container[b].degree)
406                container[container[b].child].parent=b;
407              else
408                container[b].child=-1;
409            }
410          }
411          break;
412
413        case 0:
414          --container[b].degree;
415          if( container[a].left_child ) {
416            container[b].child =
417              (0!=container[b].degree) ? container[a].parent : -1;
418          } else {
419            if( 0!=container[b].degree )
420              container[container[b].child].parent=b;
421            else
422              container[b].child=-1;
423          }
424          break;
425      }
426      container[a].parent=-1;
427      container[a].left_child=false;
428    }
429
430    void fuse(int a, int b) {
431      int child_a = container[a].child;
432      int child_b = container[b].child;
433      container[a].child=b;
434      container[b].parent=a;
435      container[b].left_child=true;
436
437      if( -1!=child_a ) {
438        container[b].child=child_a;
439        container[child_a].parent=b;
440        container[child_a].left_child=false;
441        ++container[b].degree;
442
443        if( -1!=child_b ) {
444           container[b].child=child_b;
445           container[child_b].parent=child_a;
446        }
447      }
448      else { ++container[a].degree; }
449    }
450
451    class store {
452      friend class PairingHeap;
453
454      Item name;
455      int parent;
456      int child;
457      bool left_child;
458      int degree;
459      bool in;
460      Prio prio;
461
462      store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
463    };
464  };
465
466} //namespace lemon
467
468#endif //LEMON_PAIRING_HEAP_H
469
Note: See TracBrowser for help on using the repository browser.