lemon/pairing_heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Nov 2009 19:57:02 +0100
changeset 787 c2230649a493
parent 703 bb3392fe91f2
permissions -rw-r--r--
Various doc improvements (#331)

- Add notes to the graph classes about the time of
item counting.
- Clarify the doc for run() in BFS and DFS.
- Other improvements.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     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 heaps
    24 ///\brief Pairing heap implementation.
    25 
    26 #include <vector>
    27 #include <utility>
    28 #include <functional>
    29 #include <lemon/math.h>
    30 
    31 namespace lemon {
    32 
    33   /// \ingroup heaps
    34   ///
    35   ///\brief Pairing Heap.
    36   ///
    37   /// This class implements the \e pairing \e heap data structure.
    38   /// It fully conforms to the \ref concepts::Heap "heap concept".
    39   ///
    40   /// The methods \ref increase() and \ref erase() are not efficient
    41   /// in a pairing heap. In case of many calls of these operations,
    42   /// it is better to use other heap structure, e.g. \ref BinHeap
    43   /// "binary heap".
    44   ///
    45   /// \tparam PR Type of the priorities of the items.
    46   /// \tparam IM A read-writable item map with \c int values, used
    47   /// internally to handle the cross references.
    48   /// \tparam CMP A functor class for comparing the priorities.
    49   /// The default is \c std::less<PR>.
    50 #ifdef DOXYGEN
    51   template <typename PR, typename IM, typename CMP>
    52 #else
    53   template <typename PR, typename IM, typename CMP = std::less<PR> >
    54 #endif
    55   class PairingHeap {
    56   public:
    57     /// Type of the item-int map.
    58     typedef IM ItemIntMap;
    59     /// Type of the priorities.
    60     typedef PR Prio;
    61     /// Type of the items stored in the heap.
    62     typedef typename ItemIntMap::Key Item;
    63     /// Functor type for comparing the priorities.
    64     typedef CMP Compare;
    65 
    66     /// \brief Type to represent the states of the items.
    67     ///
    68     /// Each item has a state associated to it. It can be "in heap",
    69     /// "pre-heap" or "post-heap". The latter two are indifferent from the
    70     /// heap's point of view, but may be useful to the user.
    71     ///
    72     /// The item-int map must be initialized in such way that it assigns
    73     /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
    74     enum State {
    75       IN_HEAP = 0,    ///< = 0.
    76       PRE_HEAP = -1,  ///< = -1.
    77       POST_HEAP = -2  ///< = -2.
    78     };
    79 
    80   private:
    81     class store;
    82 
    83     std::vector<store> _data;
    84     int _min;
    85     ItemIntMap &_iim;
    86     Compare _comp;
    87     int _num_items;
    88 
    89   public:
    90     /// \brief Constructor.
    91     ///
    92     /// Constructor.
    93     /// \param map A map that assigns \c int values to the items.
    94     /// It is used internally to handle the cross references.
    95     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    96     explicit PairingHeap(ItemIntMap &map)
    97       : _min(0), _iim(map), _num_items(0) {}
    98 
    99     /// \brief Constructor.
   100     ///
   101     /// Constructor.
   102     /// \param map A map that assigns \c int values to the items.
   103     /// It is used internally to handle the cross references.
   104     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   105     /// \param comp The function object used for comparing the priorities.
   106     PairingHeap(ItemIntMap &map, const Compare &comp)
   107       : _min(0), _iim(map), _comp(comp), _num_items(0) {}
   108 
   109     /// \brief The number of items stored in the heap.
   110     ///
   111     /// This function returns the number of items stored in the heap.
   112     int size() const { return _num_items; }
   113 
   114     /// \brief Check if the heap is empty.
   115     ///
   116     /// This function returns \c true if the heap is empty.
   117     bool empty() const { return _num_items==0; }
   118 
   119     /// \brief Make the heap empty.
   120     ///
   121     /// This functon makes the heap empty.
   122     /// It does not change the cross reference map. If you want to reuse
   123     /// a heap that is not surely empty, you should first clear it and
   124     /// then you should set the cross reference map to \c PRE_HEAP
   125     /// for each item.
   126     void clear() {
   127       _data.clear();
   128       _min = 0;
   129       _num_items = 0;
   130     }
   131 
   132     /// \brief Set the priority of an item or insert it, if it is
   133     /// not stored in the heap.
   134     ///
   135     /// This method sets the priority of the given item if it is
   136     /// already stored in the heap. Otherwise it inserts the given
   137     /// item into the heap with the given priority.
   138     /// \param item The item.
   139     /// \param value The priority.
   140     void set (const Item& item, const Prio& value) {
   141       int i=_iim[item];
   142       if ( i>=0 && _data[i].in ) {
   143         if ( _comp(value, _data[i].prio) ) decrease(item, value);
   144         if ( _comp(_data[i].prio, value) ) increase(item, value);
   145       } else push(item, value);
   146     }
   147 
   148     /// \brief Insert an item into the heap with the given priority.
   149     ///
   150     /// This function inserts the given item into the heap with the
   151     /// given priority.
   152     /// \param item The item to insert.
   153     /// \param value The priority of the item.
   154     /// \pre \e item must not be stored in the heap.
   155     void push (const Item& item, const Prio& value) {
   156       int i=_iim[item];
   157       if( i<0 ) {
   158         int s=_data.size();
   159         _iim.set(item, s);
   160         store st;
   161         st.name=item;
   162         _data.push_back(st);
   163         i=s;
   164       } else {
   165         _data[i].parent=_data[i].child=-1;
   166         _data[i].left_child=false;
   167         _data[i].degree=0;
   168         _data[i].in=true;
   169       }
   170 
   171       _data[i].prio=value;
   172 
   173       if ( _num_items!=0 ) {
   174         if ( _comp( value, _data[_min].prio) ) {
   175           fuse(i,_min);
   176           _min=i;
   177         }
   178         else fuse(_min,i);
   179       }
   180       else _min=i;
   181 
   182       ++_num_items;
   183     }
   184 
   185     /// \brief Return the item having minimum priority.
   186     ///
   187     /// This function returns the item having minimum priority.
   188     /// \pre The heap must be non-empty.
   189     Item top() const { return _data[_min].name; }
   190 
   191     /// \brief The minimum priority.
   192     ///
   193     /// This function returns the minimum priority.
   194     /// \pre The heap must be non-empty.
   195     const Prio& prio() const { return _data[_min].prio; }
   196 
   197     /// \brief The priority of the given item.
   198     ///
   199     /// This function returns the priority of the given item.
   200     /// \param item The item.
   201     /// \pre \e item must be in the heap.
   202     const Prio& operator[](const Item& item) const {
   203       return _data[_iim[item]].prio;
   204     }
   205 
   206     /// \brief Remove the item having minimum priority.
   207     ///
   208     /// This function removes the item having minimum priority.
   209     /// \pre The heap must be non-empty.
   210     void pop() {
   211       std::vector<int> trees;
   212       int i=0, child_right = 0;
   213       _data[_min].in=false;
   214 
   215       if( -1!=_data[_min].child ) {
   216         i=_data[_min].child;
   217         trees.push_back(i);
   218         _data[i].parent = -1;
   219         _data[_min].child = -1;
   220 
   221         int ch=-1;
   222         while( _data[i].child!=-1 ) {
   223           ch=_data[i].child;
   224           if( _data[ch].left_child && i==_data[ch].parent ) {
   225             break;
   226           } else {
   227             if( _data[ch].left_child ) {
   228               child_right=_data[ch].parent;
   229               _data[ch].parent = i;
   230               --_data[i].degree;
   231             }
   232             else {
   233               child_right=ch;
   234               _data[i].child=-1;
   235               _data[i].degree=0;
   236             }
   237             _data[child_right].parent = -1;
   238             trees.push_back(child_right);
   239             i = child_right;
   240           }
   241         }
   242 
   243         int num_child = trees.size();
   244         int other;
   245         for( i=0; i<num_child-1; i+=2 ) {
   246           if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
   247             other=trees[i];
   248             trees[i]=trees[i+1];
   249             trees[i+1]=other;
   250           }
   251           fuse( trees[i], trees[i+1] );
   252         }
   253 
   254         i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
   255         while(i>=2) {
   256           if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
   257             other=trees[i];
   258             trees[i]=trees[i-2];
   259             trees[i-2]=other;
   260           }
   261           fuse( trees[i-2], trees[i] );
   262           i-=2;
   263         }
   264         _min = trees[0];
   265       }
   266       else {
   267         _min = _data[_min].child;
   268       }
   269 
   270       if (_min >= 0) _data[_min].left_child = false;
   271       --_num_items;
   272     }
   273 
   274     /// \brief Remove the given item from the heap.
   275     ///
   276     /// This function removes the given item from the heap if it is
   277     /// already stored.
   278     /// \param item The item to delete.
   279     /// \pre \e item must be in the heap.
   280     void erase (const Item& item) {
   281       int i=_iim[item];
   282       if ( i>=0 && _data[i].in ) {
   283         decrease( item, _data[_min].prio-1 );
   284         pop();
   285       }
   286     }
   287 
   288     /// \brief Decrease the priority of an item to the given value.
   289     ///
   290     /// This function decreases the priority of an item to the given value.
   291     /// \param item The item.
   292     /// \param value The priority.
   293     /// \pre \e item must be stored in the heap with priority at least \e value.
   294     void decrease (Item item, const Prio& value) {
   295       int i=_iim[item];
   296       _data[i].prio=value;
   297       int p=_data[i].parent;
   298 
   299       if( _data[i].left_child && i!=_data[p].child ) {
   300         p=_data[p].parent;
   301       }
   302 
   303       if ( p!=-1 && _comp(value,_data[p].prio) ) {
   304         cut(i,p);
   305         if ( _comp(_data[_min].prio,value) ) {
   306           fuse(_min,i);
   307         } else {
   308           fuse(i,_min);
   309           _min=i;
   310         }
   311       }
   312     }
   313 
   314     /// \brief Increase the priority of an item to the given value.
   315     ///
   316     /// This function increases the priority of an item to the given value.
   317     /// \param item The item.
   318     /// \param value The priority.
   319     /// \pre \e item must be stored in the heap with priority at most \e value.
   320     void increase (Item item, const Prio& value) {
   321       erase(item);
   322       push(item,value);
   323     }
   324 
   325     /// \brief Return the state of an item.
   326     ///
   327     /// This method returns \c PRE_HEAP if the given item has never
   328     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   329     /// and \c POST_HEAP otherwise.
   330     /// In the latter case it is possible that the item will get back
   331     /// to the heap again.
   332     /// \param item The item.
   333     State state(const Item &item) const {
   334       int i=_iim[item];
   335       if( i>=0 ) {
   336         if( _data[i].in ) i=0;
   337         else i=-2;
   338       }
   339       return State(i);
   340     }
   341 
   342     /// \brief Set the state of an item in the heap.
   343     ///
   344     /// This function sets the state of the given item in the heap.
   345     /// It can be used to manually clear the heap when it is important
   346     /// to achive better time complexity.
   347     /// \param i The item.
   348     /// \param st The state. It should not be \c IN_HEAP.
   349     void state(const Item& i, State st) {
   350       switch (st) {
   351       case POST_HEAP:
   352       case PRE_HEAP:
   353         if (state(i) == IN_HEAP) erase(i);
   354         _iim[i]=st;
   355         break;
   356       case IN_HEAP:
   357         break;
   358       }
   359     }
   360 
   361   private:
   362 
   363     void cut(int a, int b) {
   364       int child_a;
   365       switch (_data[a].degree) {
   366         case 2:
   367           child_a = _data[_data[a].child].parent;
   368           if( _data[a].left_child ) {
   369             _data[child_a].left_child=true;
   370             _data[b].child=child_a;
   371             _data[child_a].parent=_data[a].parent;
   372           }
   373           else {
   374             _data[child_a].left_child=false;
   375             _data[child_a].parent=b;
   376             if( a!=_data[b].child )
   377               _data[_data[b].child].parent=child_a;
   378             else
   379               _data[b].child=child_a;
   380           }
   381           --_data[a].degree;
   382           _data[_data[a].child].parent=a;
   383           break;
   384 
   385         case 1:
   386           child_a = _data[a].child;
   387           if( !_data[child_a].left_child ) {
   388             --_data[a].degree;
   389             if( _data[a].left_child ) {
   390               _data[child_a].left_child=true;
   391               _data[child_a].parent=_data[a].parent;
   392               _data[b].child=child_a;
   393             }
   394             else {
   395               _data[child_a].left_child=false;
   396               _data[child_a].parent=b;
   397               if( a!=_data[b].child )
   398                 _data[_data[b].child].parent=child_a;
   399               else
   400                 _data[b].child=child_a;
   401             }
   402             _data[a].child=-1;
   403           }
   404           else {
   405             --_data[b].degree;
   406             if( _data[a].left_child ) {
   407               _data[b].child =
   408                 (1==_data[b].degree) ? _data[a].parent : -1;
   409             } else {
   410               if (1==_data[b].degree)
   411                 _data[_data[b].child].parent=b;
   412               else
   413                 _data[b].child=-1;
   414             }
   415           }
   416           break;
   417 
   418         case 0:
   419           --_data[b].degree;
   420           if( _data[a].left_child ) {
   421             _data[b].child =
   422               (0!=_data[b].degree) ? _data[a].parent : -1;
   423           } else {
   424             if( 0!=_data[b].degree )
   425               _data[_data[b].child].parent=b;
   426             else
   427               _data[b].child=-1;
   428           }
   429           break;
   430       }
   431       _data[a].parent=-1;
   432       _data[a].left_child=false;
   433     }
   434 
   435     void fuse(int a, int b) {
   436       int child_a = _data[a].child;
   437       int child_b = _data[b].child;
   438       _data[a].child=b;
   439       _data[b].parent=a;
   440       _data[b].left_child=true;
   441 
   442       if( -1!=child_a ) {
   443         _data[b].child=child_a;
   444         _data[child_a].parent=b;
   445         _data[child_a].left_child=false;
   446         ++_data[b].degree;
   447 
   448         if( -1!=child_b ) {
   449            _data[b].child=child_b;
   450            _data[child_b].parent=child_a;
   451         }
   452       }
   453       else { ++_data[a].degree; }
   454     }
   455 
   456     class store {
   457       friend class PairingHeap;
   458 
   459       Item name;
   460       int parent;
   461       int child;
   462       bool left_child;
   463       int degree;
   464       bool in;
   465       Prio prio;
   466 
   467       store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
   468     };
   469   };
   470 
   471 } //namespace lemon
   472 
   473 #endif //LEMON_PAIRING_HEAP_H
   474