lemon/bin_heap.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 209 765619b7cbb2
child 559 c5fd2d996909
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     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_BIN_HEAP_H
    20 #define LEMON_BIN_HEAP_H
    21 
    22 ///\ingroup auxdat
    23 ///\file
    24 ///\brief Binary Heap implementation.
    25 
    26 #include <vector>
    27 #include <utility>
    28 #include <functional>
    29 
    30 namespace lemon {
    31 
    32   ///\ingroup auxdat
    33   ///
    34   ///\brief A Binary Heap implementation.
    35   ///
    36   ///This class implements the \e binary \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   ///\tparam _Prio Type of the priority of the items.
    43   ///\tparam _ItemIntMap A read and writable Item int map, used internally
    44   ///to handle the cross references.
    45   ///\tparam _Compare A class for the ordering of the priorities. The
    46   ///default is \c std::less<_Prio>.
    47   ///
    48   ///\sa FibHeap
    49   ///\sa Dijkstra
    50   template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
    52   class BinHeap {
    53 
    54   public:
    55     ///\e
    56     typedef _ItemIntMap ItemIntMap;
    57     ///\e
    58     typedef _Prio Prio;
    59     ///\e
    60     typedef typename ItemIntMap::Key Item;
    61     ///\e
    62     typedef std::pair<Item,Prio> Pair;
    63     ///\e
    64     typedef _Compare Compare;
    65 
    66     /// \brief Type to represent the items states.
    67     ///
    68     /// Each Item element have a state associated to it. It may 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 ItemIntMap \e should be initialized in such way that it maps
    73     /// PRE_HEAP (-1) to any element to be put in the heap...
    74     enum State {
    75       IN_HEAP = 0,
    76       PRE_HEAP = -1,
    77       POST_HEAP = -2
    78     };
    79 
    80   private:
    81     std::vector<Pair> data;
    82     Compare comp;
    83     ItemIntMap &iim;
    84 
    85   public:
    86     /// \brief The constructor.
    87     ///
    88     /// The constructor.
    89     /// \param _iim should be given to the constructor, since it is used
    90     /// internally to handle the cross references. The value of the map
    91     /// should be PRE_HEAP (-1) for each element.
    92     explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93 
    94     /// \brief The constructor.
    95     ///
    96     /// The constructor.
    97     /// \param _iim should be given to the constructor, since it is used
    98     /// internally to handle the cross references. The value of the map
    99     /// should be PRE_HEAP (-1) for each element.
   100     ///
   101     /// \param _comp The comparator function object.
   102     BinHeap(ItemIntMap &_iim, const Compare &_comp)
   103       : iim(_iim), comp(_comp) {}
   104 
   105 
   106     /// The number of items stored in the heap.
   107     ///
   108     /// \brief Returns the number of items stored in the heap.
   109     int size() const { return data.size(); }
   110 
   111     /// \brief Checks if the heap stores no items.
   112     ///
   113     /// Returns \c true if and only if the heap stores no items.
   114     bool empty() const { return data.empty(); }
   115 
   116     /// \brief Make empty this heap.
   117     ///
   118     /// Make empty this heap. It does not change the cross reference map.
   119     /// If you want to reuse what is not surely empty you should first clear
   120     /// the heap and after that you should set the cross reference map for
   121     /// each item to \c PRE_HEAP.
   122     void clear() {
   123       data.clear();
   124     }
   125 
   126   private:
   127     static int parent(int i) { return (i-1)/2; }
   128 
   129     static int second_child(int i) { return 2*i+2; }
   130     bool less(const Pair &p1, const Pair &p2) const {
   131       return comp(p1.second, p2.second);
   132     }
   133 
   134     int bubble_up(int hole, Pair p) {
   135       int par = parent(hole);
   136       while( hole>0 && less(p,data[par]) ) {
   137         move(data[par],hole);
   138         hole = par;
   139         par = parent(hole);
   140       }
   141       move(p, hole);
   142       return hole;
   143     }
   144 
   145     int bubble_down(int hole, Pair p, int length) {
   146       int child = second_child(hole);
   147       while(child < length) {
   148         if( less(data[child-1], data[child]) ) {
   149           --child;
   150         }
   151         if( !less(data[child], p) )
   152           goto ok;
   153         move(data[child], hole);
   154         hole = child;
   155         child = second_child(hole);
   156       }
   157       child--;
   158       if( child<length && less(data[child], p) ) {
   159         move(data[child], hole);
   160         hole=child;
   161       }
   162     ok:
   163       move(p, hole);
   164       return hole;
   165     }
   166 
   167     void move(const Pair &p, int i) {
   168       data[i] = p;
   169       iim.set(p.first, i);
   170     }
   171 
   172   public:
   173     /// \brief Insert a pair of item and priority into the heap.
   174     ///
   175     /// Adds \c p.first to the heap with priority \c p.second.
   176     /// \param p The pair to insert.
   177     void push(const Pair &p) {
   178       int n = data.size();
   179       data.resize(n+1);
   180       bubble_up(n, p);
   181     }
   182 
   183     /// \brief Insert an item into the heap with the given heap.
   184     ///
   185     /// Adds \c i to the heap with priority \c p.
   186     /// \param i The item to insert.
   187     /// \param p The priority of the item.
   188     void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   189 
   190     /// \brief Returns the item with minimum priority relative to \c Compare.
   191     ///
   192     /// This method returns the item with minimum priority relative to \c
   193     /// Compare.
   194     /// \pre The heap must be nonempty.
   195     Item top() const {
   196       return data[0].first;
   197     }
   198 
   199     /// \brief Returns the minimum priority relative to \c Compare.
   200     ///
   201     /// It returns the minimum priority relative to \c Compare.
   202     /// \pre The heap must be nonempty.
   203     Prio prio() const {
   204       return data[0].second;
   205     }
   206 
   207     /// \brief Deletes the item with minimum priority relative to \c Compare.
   208     ///
   209     /// This method deletes the item with minimum priority relative to \c
   210     /// Compare from the heap.
   211     /// \pre The heap must be non-empty.
   212     void pop() {
   213       int n = data.size()-1;
   214       iim.set(data[0].first, POST_HEAP);
   215       if (n > 0) {
   216         bubble_down(0, data[n], n);
   217       }
   218       data.pop_back();
   219     }
   220 
   221     /// \brief Deletes \c i from the heap.
   222     ///
   223     /// This method deletes item \c i from the heap.
   224     /// \param i The item to erase.
   225     /// \pre The item should be in the heap.
   226     void erase(const Item &i) {
   227       int h = iim[i];
   228       int n = data.size()-1;
   229       iim.set(data[h].first, POST_HEAP);
   230       if( h < n ) {
   231         if ( bubble_up(h, data[n]) == h) {
   232           bubble_down(h, data[n], n);
   233         }
   234       }
   235       data.pop_back();
   236     }
   237 
   238 
   239     /// \brief Returns the priority of \c i.
   240     ///
   241     /// This function returns the priority of item \c i.
   242     /// \pre \c i must be in the heap.
   243     /// \param i The item.
   244     Prio operator[](const Item &i) const {
   245       int idx = iim[i];
   246       return data[idx].second;
   247     }
   248 
   249     /// \brief \c i gets to the heap with priority \c p independently
   250     /// if \c i was already there.
   251     ///
   252     /// This method calls \ref push(\c i, \c p) if \c i is not stored
   253     /// in the heap and sets the priority of \c i to \c p otherwise.
   254     /// \param i The item.
   255     /// \param p The priority.
   256     void set(const Item &i, const Prio &p) {
   257       int idx = iim[i];
   258       if( idx < 0 ) {
   259         push(i,p);
   260       }
   261       else if( comp(p, data[idx].second) ) {
   262         bubble_up(idx, Pair(i,p));
   263       }
   264       else {
   265         bubble_down(idx, Pair(i,p), data.size());
   266       }
   267     }
   268 
   269     /// \brief Decreases the priority of \c i to \c p.
   270     ///
   271     /// This method decreases the priority of item \c i to \c p.
   272     /// \pre \c i must be stored in the heap with priority at least \c
   273     /// p relative to \c Compare.
   274     /// \param i The item.
   275     /// \param p The priority.
   276     void decrease(const Item &i, const Prio &p) {
   277       int idx = iim[i];
   278       bubble_up(idx, Pair(i,p));
   279     }
   280 
   281     /// \brief Increases the priority of \c i to \c p.
   282     ///
   283     /// This method sets the priority of item \c i to \c p.
   284     /// \pre \c i must be stored in the heap with priority at most \c
   285     /// p relative to \c Compare.
   286     /// \param i The item.
   287     /// \param p The priority.
   288     void increase(const Item &i, const Prio &p) {
   289       int idx = iim[i];
   290       bubble_down(idx, Pair(i,p), data.size());
   291     }
   292 
   293     /// \brief Returns if \c item is in, has already been in, or has
   294     /// never been in the heap.
   295     ///
   296     /// This method returns PRE_HEAP if \c item has never been in the
   297     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   298     /// otherwise. In the latter case it is possible that \c item will
   299     /// get back to the heap again.
   300     /// \param i The item.
   301     State state(const Item &i) const {
   302       int s = iim[i];
   303       if( s>=0 )
   304         s=0;
   305       return State(s);
   306     }
   307 
   308     /// \brief Sets the state of the \c item in the heap.
   309     ///
   310     /// Sets the state of the \c item in the heap. It can be used to
   311     /// manually clear the heap when it is important to achive the
   312     /// better time complexity.
   313     /// \param i The item.
   314     /// \param st The state. It should not be \c IN_HEAP.
   315     void state(const Item& i, State st) {
   316       switch (st) {
   317       case POST_HEAP:
   318       case PRE_HEAP:
   319         if (state(i) == IN_HEAP) {
   320           erase(i);
   321         }
   322         iim[i] = st;
   323         break;
   324       case IN_HEAP:
   325         break;
   326       }
   327     }
   328 
   329     /// \brief Replaces an item in the heap.
   330     ///
   331     /// The \c i item is replaced with \c j item. The \c i item should
   332     /// be in the heap, while the \c j should be out of the heap. The
   333     /// \c i item will out of the heap and \c j will be in the heap
   334     /// with the same prioriority as prevoiusly the \c i item.
   335     void replace(const Item& i, const Item& j) {
   336       int idx = iim[i];
   337       iim.set(i, iim[j]);
   338       iim.set(j, idx);
   339       data[idx].first = j;
   340     }
   341 
   342   }; // class BinHeap
   343 
   344 } // namespace lemon
   345 
   346 #endif // LEMON_BIN_HEAP_H