COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bin_heap.h

    r758 r730  
    2020#define LEMON_BIN_HEAP_H
    2121
    22 ///\ingroup heaps
     22///\ingroup auxdat
    2323///\file
    24 ///\brief Binary heap implementation.
     24///\brief Binary Heap implementation.
    2525
    2626#include <vector>
    … …  
    3030namespace lemon {
    3131
    32   /// \ingroup heaps
    33   ///
    34   /// \brief Binary heap data structure.
    35   ///
    36   /// This class implements the \e binary \e heap data structure.
    37   /// It fully conforms to the \ref concepts::Heap "heap concept".
    38   ///
    39   /// \tparam PR Type of the priorities of the items.
    40   /// \tparam IM A read-writable item map with \c int values, used
    41   /// internally to handle the cross references.
    42   /// \tparam CMP A functor class for comparing the priorities.
    43   /// The default is \c std::less<PR>.
    44 #ifdef DOXYGEN
    45   template <typename PR, typename IM, typename CMP>
    46 #else
     32  ///\ingroup auxdat
     33  ///
     34  ///\brief A Binary Heap implementation.
     35  ///
     36  ///This class implements the \e binary \e heap data structure.
     37  ///
     38  ///A \e heap is a data structure for storing items with specified values
     39  ///called \e priorities in such a way that finding the item with minimum
     40  ///priority is efficient. \c CMP specifies the ordering of the priorities.
     41  ///In a heap one can change the priority of an item, add or erase an
     42  ///item, etc.
     43  ///
     44  ///\tparam PR Type of the priority of the items.
     45  ///\tparam IM A read and writable item map with int values, used internally
     46  ///to handle the cross references.
     47  ///\tparam CMP A functor class for the ordering of the priorities.
     48  ///The default is \c std::less<PR>.
     49  ///
     50  ///\sa FibHeap
     51  ///\sa Dijkstra
    4752  template <typename PR, typename IM, typename CMP = std::less<PR> >
    48 #endif
    4953  class BinHeap {
     54
    5055  public:
    51 
    52     /// Type of the item-int map.
     56    ///\e
    5357    typedef IM ItemIntMap;
    54     /// Type of the priorities.
     58    ///\e
    5559    typedef PR Prio;
    56     /// Type of the items stored in the heap.
     60    ///\e
    5761    typedef typename ItemIntMap::Key Item;
    58     /// Type of the item-priority pairs.
     62    ///\e
    5963    typedef std::pair<Item,Prio> Pair;
    60     /// Functor type for comparing the priorities.
     64    ///\e
    6165    typedef CMP Compare;
    6266
    63     /// \brief Type to represent the states of the items.
    64     ///
    65     /// Each item has a state associated to it. It can be "in heap",
    66     /// "pre-heap" or "post-heap". The latter two are indifferent from the
     67    /// \brief Type to represent the items states.
     68    ///
     69    /// Each Item element have a state associated to it. It may be "in heap",
     70    /// "pre heap" or "post heap". The latter two are indifferent from the
    6771    /// heap's point of view, but may be useful to the user.
    6872    ///
    … …  
    8185
    8286  public:
    83 
    84     /// \brief Constructor.
    85     ///
    86     /// Constructor.
    87     /// \param map A map that assigns \c int values to the items.
    88     /// It is used internally to handle the cross references.
    89     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
     87    /// \brief The constructor.
     88    ///
     89    /// The constructor.
     90    /// \param map should be given to the constructor, since it is used
     91    /// internally to handle the cross references. The value of the map
     92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
    9093    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
    9194
    92     /// \brief Constructor.
    93     ///
    94     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     /// \param comp The function object used for comparing the priorities.
     95    /// \brief The constructor.
     96    ///
     97    /// The constructor.
     98    /// \param map should be given to the constructor, since it is used
     99    /// internally to handle the cross references. The value of the map
     100    /// should be PRE_HEAP (-1) for each element.
     101    ///
     102    /// \param comp The comparator function object.
    99103    BinHeap(ItemIntMap &map, const Compare &comp)
    100104      : _iim(map), _comp(comp) {}
    101105
    102106
    103     /// \brief The number of items stored in the heap.
    104     ///
    105     /// This function returns the number of items stored in the heap.
     107    /// The number of items stored in the heap.
     108    ///
     109    /// \brief Returns the number of items stored in the heap.
    106110    int size() const { return _data.size(); }
    107111
    108     /// \brief Check if the heap is empty.
    109     ///
    110     /// This function returns \c true if the heap is empty.
     112    /// \brief Checks if the heap stores no items.
     113    ///
     114    /// Returns \c true if and only if the heap stores no items.
    111115    bool empty() const { return _data.empty(); }
    112116
    113     /// \brief Make the heap empty.
    114     ///
    115     /// This functon makes the heap empty.
    116     /// It does not change the cross reference map. If you want to reuse
    117     /// a heap that is not surely empty, you should first clear it and
    118     /// then you should set the cross reference map to \c PRE_HEAP
    119     /// for each item.
     117    /// \brief Make empty this heap.
     118    ///
     119    /// Make empty this heap. It does not change the cross reference map.
     120    /// If you want to reuse what is not surely empty you should first clear
     121    /// the heap and after that you should set the cross reference map for
     122    /// each item to \c PRE_HEAP.
    120123    void clear() {
    121124      _data.clear();
    … …  
    125128    static int parent(int i) { return (i-1)/2; }
    126129
    127     static int secondChild(int i) { return 2*i+2; }
     130    static int second_child(int i) { return 2*i+2; }
    128131    bool less(const Pair &p1, const Pair &p2) const {
    129132      return _comp(p1.second, p2.second);
    130133    }
    131134
    132     int bubbleUp(int hole, Pair p) {
     135    int bubble_up(int hole, Pair p) {
    133136      int par = parent(hole);
    134137      while( hole>0 && less(p,_data[par]) ) {
    … …  
    141144    }
    142145
    143     int bubbleDown(int hole, Pair p, int length) {
    144       int child = secondChild(hole);
     146    int bubble_down(int hole, Pair p, int length) {
     147      int child = second_child(hole);
    145148      while(child < length) {
    146149        if( less(_data[child-1], _data[child]) ) {
    … …  
    151154        move(_data[child], hole);
    152155        hole = child;
    153         child = secondChild(hole);
     156        child = second_child(hole);
    154157      }
    155158      child--;
    … …  
    169172
    170173  public:
    171 
    172174    /// \brief Insert a pair of item and priority into the heap.
    173175    ///
    174     /// This function inserts \c p.first to the heap with priority
    175     /// \c p.second.
     176    /// Adds \c p.first to the heap with priority \c p.second.
    176177    /// \param p The pair to insert.
    177     /// \pre \c p.first must not be stored in the heap.
    178178    void push(const Pair &p) {
    179179      int n = _data.size();
    180180      _data.resize(n+1);
    181       bubbleUp(n, p);
    182     }
    183 
    184     /// \brief Insert an item into the heap with the given priority.
    185     ///
    186     /// This function inserts the given item into the heap with the
    187     /// given priority.
     181      bubble_up(n, p);
     182    }
     183
     184    /// \brief Insert an item into the heap with the given heap.
     185    ///
     186    /// Adds \c i to the heap with priority \c p.
    188187    /// \param i The item to insert.
    189188    /// \param p The priority of the item.
    190     /// \pre \e i must not be stored in the heap.
    191189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
    192190
    193     /// \brief Return the item having minimum priority.
    194     ///
    195     /// This function returns the item having minimum priority.
    196     /// \pre The heap must be non-empty.
     191    /// \brief Returns the item with minimum priority relative to \c Compare.
     192    ///
     193    /// This method returns the item with minimum priority relative to \c
     194    /// Compare.
     195    /// \pre The heap must be nonempty.
    197196    Item top() const {
    198197      return _data[0].first;
    199198    }
    200199
    201     /// \brief The minimum priority.
    202     ///
    203     /// This function returns the minimum priority.
    204     /// \pre The heap must be non-empty.
     200    /// \brief Returns the minimum priority relative to \c Compare.
     201    ///
     202    /// It returns the minimum priority relative to \c Compare.
     203    /// \pre The heap must be nonempty.
    205204    Prio prio() const {
    206205      return _data[0].second;
    207206    }
    208207
    209     /// \brief Remove the item having minimum priority.
    210     ///
    211     /// This function removes the item having minimum priority.
     208    /// \brief Deletes the item with minimum priority relative to \c Compare.
     209    ///
     210    /// This method deletes the item with minimum priority relative to \c
     211    /// Compare from the heap.
    212212    /// \pre The heap must be non-empty.
    213213    void pop() {
    … …  
    215215      _iim.set(_data[0].first, POST_HEAP);
    216216      if (n > 0) {
    217         bubbleDown(0, _data[n], n);
     217        bubble_down(0, _data[n], n);
    218218      }
    219219      _data.pop_back();
    220220    }
    221221
    222     /// \brief Remove the given item from the heap.
    223     ///
    224     /// This function removes the given item from the heap if it is
    225     /// already stored.
    226     /// \param i The item to delete.
    227     /// \pre \e i must be in the heap.
     222    /// \brief Deletes \c i from the heap.
     223    ///
     224    /// This method deletes item \c i from the heap.
     225    /// \param i The item to erase.
     226    /// \pre The item should be in the heap.
    228227    void erase(const Item &i) {
    229228      int h = _iim[i];
    … …  
    231230      _iim.set(_data[h].first, POST_HEAP);
    232231      if( h < n ) {
    233         if ( bubbleUp(h, _data[n]) == h) {
    234           bubbleDown(h, _data[n], n);
     232        if ( bubble_up(h, _data[n]) == h) {
     233          bubble_down(h, _data[n], n);
    235234        }
    236235      }
    … …  
    238237    }
    239238
    240     /// \brief The priority of the given item.
    241     ///
    242     /// This function returns the priority of the given item.
    243     /// \param i The item.
    244     /// \pre \e i must be in the heap.
     239
     240    /// \brief Returns the priority of \c i.
     241    ///
     242    /// This function returns the priority of item \c i.
     243    /// \param i The item.
     244    /// \pre \c i must be in the heap.
    245245    Prio operator[](const Item &i) const {
    246246      int idx = _iim[i];
    … …  
    248248    }
    249249
    250     /// \brief Set the priority of an item or insert it, if it is
    251     /// not stored in the heap.
    252     ///
    253     /// This method sets the priority of the given item if it is
    254     /// already stored in the heap. Otherwise it inserts the given
    255     /// item into the heap with the given priority.
     250    /// \brief \c i gets to the heap with priority \c p independently
     251    /// if \c i was already there.
     252    ///
     253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
     254    /// in the heap and sets the priority of \c i to \c p otherwise.
    256255    /// \param i The item.
    257256    /// \param p The priority.
    … …  
    262261      }
    263262      else if( _comp(p, _data[idx].second) ) {
    264         bubbleUp(idx, Pair(i,p));
     263        bubble_up(idx, Pair(i,p));
    265264      }
    266265      else {
    267         bubbleDown(idx, Pair(i,p), _data.size());
    268       }
    269     }
    270 
    271     /// \brief Decrease the priority of an item to the given value.
    272     ///
    273     /// This function decreases the priority of an item to the given value.
     266        bubble_down(idx, Pair(i,p), _data.size());
     267      }
     268    }
     269
     270    /// \brief Decreases the priority of \c i to \c p.
     271    ///
     272    /// This method decreases the priority of item \c i to \c p.
    274273    /// \param i The item.
    275274    /// \param p The priority.
    276     /// \pre \e i must be stored in the heap with priority at least \e p.
     275    /// \pre \c i must be stored in the heap with priority at least \c
     276    /// p relative to \c Compare.
    277277    void decrease(const Item &i, const Prio &p) {
    278278      int idx = _iim[i];
    279       bubbleUp(idx, Pair(i,p));
    280     }
    281 
    282     /// \brief Increase the priority of an item to the given value.
    283     ///
    284     /// This function increases the priority of an item to the given value.
     279      bubble_up(idx, Pair(i,p));
     280    }
     281
     282    /// \brief Increases the priority of \c i to \c p.
     283    ///
     284    /// This method sets the priority of item \c i to \c p.
    285285    /// \param i The item.
    286286    /// \param p The priority.
    287     /// \pre \e i must be stored in the heap with priority at most \e p.
     287    /// \pre \c i must be stored in the heap with priority at most \c
     288    /// p relative to \c Compare.
    288289    void increase(const Item &i, const Prio &p) {
    289290      int idx = _iim[i];
    290       bubbleDown(idx, Pair(i,p), _data.size());
    291     }
    292 
    293     /// \brief Return the state of an item.
    294     ///
    295     /// This method returns \c PRE_HEAP if the given item has never
    296     /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
    297     /// and \c POST_HEAP otherwise.
    298     /// In the latter case it is possible that the item will get back
    299     /// to the heap again.
     291      bubble_down(idx, Pair(i,p), _data.size());
     292    }
     293
     294    /// \brief Returns if \c item is in, has already been in, or has
     295    /// never been in the heap.
     296    ///
     297    /// This method returns PRE_HEAP if \c item has never been in the
     298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
     299    /// otherwise. In the latter case it is possible that \c item will
     300    /// get back to the heap again.
    300301    /// \param i The item.
    301302    State state(const Item &i) const {
    … …  
    306307    }
    307308
    308     /// \brief Set the state of an item in the heap.
    309     ///
    310     /// This function sets the state of the given item in the heap.
    311     /// It can be used to manually clear the heap when it is important
    312     /// to achive better time complexity.
     309    /// \brief Sets the state of the \c item in the heap.
     310    ///
     311    /// Sets the state of the \c item in the heap. It can be used to
     312    /// manually clear the heap when it is important to achive the
     313    /// better time complexity.
    313314    /// \param i The item.
    314315    /// \param st The state. It should not be \c IN_HEAP.
    … …  
    327328    }
    328329
    329     /// \brief Replace an item in the heap.
    330     ///
    331     /// This function replaces item \c i with item \c j.
    332     /// Item \c i must be in the heap, while \c j must be out of the heap.
    333     /// After calling this method, item \c i will be out of the
    334     /// heap and \c j will be in the heap with the same prioriority
    335     /// as item \c i had before.
     330    /// \brief Replaces an item in the heap.
     331    ///
     332    /// The \c i item is replaced with \c j item. The \c i item should
     333    /// be in the heap, while the \c j should be out of the heap. The
     334    /// \c i item will out of the heap and \c j will be in the heap
     335    /// with the same prioriority as prevoiusly the \c i item.
    336336    void replace(const Item& i, const Item& j) {
    337337      int idx = _iim[i];
Note: See TracChangeset for help on using the changeset viewer.