lemon/fourary_heap.h
changeset 748 d1a9224f1e30
child 750 bb3392fe91f2
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/fourary_heap.h	Thu Jul 09 02:38:01 2009 +0200
     1.3 @@ -0,0 +1,350 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_FOURARY_HEAP_H
    1.23 +#define LEMON_FOURARY_HEAP_H
    1.24 +
    1.25 +///\ingroup auxdat
    1.26 +///\file
    1.27 +///\brief 4ary Heap implementation.
    1.28 +
    1.29 +#include <iostream>
    1.30 +#include <vector>
    1.31 +#include <utility>
    1.32 +#include <functional>
    1.33 +
    1.34 +namespace lemon {
    1.35 +
    1.36 +  ///\ingroup auxdat
    1.37 +  ///
    1.38 +  ///\brief A 4ary Heap implementation.
    1.39 +  ///
    1.40 +  ///This class implements the \e 4ary \e heap data structure. A \e heap
    1.41 +  ///is a data structure for storing items with specified values called \e
    1.42 +  ///priorities in such a way that finding the item with minimum priority is
    1.43 +  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
    1.44 +  ///one can change the priority of an item, add or erase an item, etc.
    1.45 +  ///
    1.46 +  ///\param _Prio Type of the priority of the items.
    1.47 +  ///\param _ItemIntMap A read and writable Item int map, used internally
    1.48 +  ///to handle the cross references.
    1.49 +  ///\param _Compare A class for the ordering of the priorities. The
    1.50 +  ///default is \c std::less<_Prio>.
    1.51 +  ///
    1.52 +  ///\sa FibHeap
    1.53 +  ///\sa Dijkstra
    1.54 +  ///\author Dorian Batha
    1.55 +
    1.56 +  template <typename _Prio, typename _ItemIntMap,
    1.57 +            typename _Compare = std::less<_Prio> >
    1.58 +
    1.59 +  class FouraryHeap {
    1.60 +
    1.61 +  public:
    1.62 +    ///\e
    1.63 +    typedef _ItemIntMap ItemIntMap;
    1.64 +    ///\e
    1.65 +    typedef _Prio Prio;
    1.66 +    ///\e
    1.67 +    typedef typename ItemIntMap::Key Item;
    1.68 +    ///\e
    1.69 +    typedef std::pair<Item,Prio> Pair;
    1.70 +    ///\e
    1.71 +    typedef _Compare Compare;
    1.72 +
    1.73 +    /// \brief Type to represent the items states.
    1.74 +    ///
    1.75 +    /// Each Item element have a state associated to it. It may be "in heap",
    1.76 +    /// "pre heap" or "post heap". The latter two are indifferent from the
    1.77 +    /// heap's point of view, but may be useful to the user.
    1.78 +    ///
    1.79 +    /// The ItemIntMap \e should be initialized in such way that it maps
    1.80 +    /// PRE_HEAP (-1) to any element to be put in the heap...
    1.81 +    enum State {
    1.82 +      IN_HEAP = 0,
    1.83 +      PRE_HEAP = -1,
    1.84 +      POST_HEAP = -2
    1.85 +    };
    1.86 +
    1.87 +  private:
    1.88 +    std::vector<Pair> data;
    1.89 +    Compare comp;
    1.90 +    ItemIntMap &iim;
    1.91 +
    1.92 +  public:
    1.93 +    /// \brief The constructor.
    1.94 +    ///
    1.95 +    /// The constructor.
    1.96 +    /// \param _iim should be given to the constructor, since it is used
    1.97 +    /// internally to handle the cross references. The value of the map
    1.98 +    /// should be PRE_HEAP (-1) for each element.
    1.99 +    explicit FouraryHeap(ItemIntMap &_iim) : iim(_iim) {}
   1.100 +
   1.101 +    /// \brief The constructor.
   1.102 +    ///
   1.103 +    /// The constructor.
   1.104 +    /// \param _iim should be given to the constructor, since it is used
   1.105 +    /// internally to handle the cross references. The value of the map
   1.106 +    /// should be PRE_HEAP (-1) for each element.
   1.107 +    ///
   1.108 +    /// \param _comp The comparator function object.
   1.109 +    FouraryHeap(ItemIntMap &_iim, const Compare &_comp)
   1.110 +      : iim(_iim), comp(_comp) {}
   1.111 +
   1.112 +    /// The number of items stored in the heap.
   1.113 +    ///
   1.114 +    /// \brief Returns the number of items stored in the heap.
   1.115 +    int size() const { return data.size(); }
   1.116 +
   1.117 +    /// \brief Checks if the heap stores no items.
   1.118 +    ///
   1.119 +    /// Returns \c true if and only if the heap stores no items.
   1.120 +    bool empty() const { return data.empty(); }
   1.121 +
   1.122 +    /// \brief Make empty this heap.
   1.123 +    ///
   1.124 +    /// Make empty this heap. It does not change the cross reference map.
   1.125 +    /// If you want to reuse what is not surely empty you should first clear
   1.126 +    /// the heap and after that you should set the cross reference map for
   1.127 +    /// each item to \c PRE_HEAP.
   1.128 +    void clear() { data.clear(); }
   1.129 +
   1.130 +  private:
   1.131 +    static int parent(int i) { return (i-1)/4; }
   1.132 +    static int firstChild(int i) { return 4*i+1; }
   1.133 +
   1.134 +    bool less(const Pair &p1, const Pair &p2) const {
   1.135 +      return comp(p1.second, p2.second);
   1.136 +    }
   1.137 +
   1.138 +    int find_min(const int child, const int length) {
   1.139 +      int min=child;
   1.140 +      if( child+3<length ) {
   1.141 +        if( less(data[child+3], data[min]) )
   1.142 +          min=child+3;
   1.143 +        if( less(data[child+2], data[min]) )
   1.144 +          min=child+2;
   1.145 +        if( less(data[child+1], data[min]) )
   1.146 +          min=child+1;
   1.147 +      }
   1.148 +      else if( child+2<length ) {
   1.149 +        if( less(data[child+2], data[min]) )
   1.150 +          min=child+2;
   1.151 +        if( less(data[child+1], data[min]) )
   1.152 +          min=child+1;
   1.153 +      }
   1.154 +      else if( child+1<length ) {
   1.155 +        if( less(data[child+1], data[min]) )
   1.156 +          min=child+1;
   1.157 +      }
   1.158 +      return min;
   1.159 +    }
   1.160 +
   1.161 +    void bubble_up(int hole, Pair p) {
   1.162 +      int par = parent(hole);
   1.163 +      while( hole>0 && less(p,data[par]) ) {
   1.164 +        move(data[par],hole);
   1.165 +        hole = par;
   1.166 +        par = parent(hole);
   1.167 +      }
   1.168 +      move(p, hole);
   1.169 +    }
   1.170 +
   1.171 +    void bubble_down(int hole, Pair p, int length) {
   1.172 +      int child = firstChild(hole);
   1.173 +      while( child<length && length>1 ) {
   1.174 +        child = find_min(child,length);
   1.175 +        if( !less(data[child], p) )
   1.176 +          goto ok;
   1.177 +        move(data[child], hole);
   1.178 +        hole = child;
   1.179 +        child = firstChild(hole);
   1.180 +      }
   1.181 +    ok:
   1.182 +      move(p, hole);
   1.183 +    }
   1.184 +
   1.185 +    void move(const Pair &p, int i) {
   1.186 +      data[i] = p;
   1.187 +      iim.set(p.first, i);
   1.188 +    }
   1.189 +
   1.190 +  public:
   1.191 +
   1.192 +    /// \brief Insert a pair of item and priority into the heap.
   1.193 +    ///
   1.194 +    /// Adds \c p.first to the heap with priority \c p.second.
   1.195 +    /// \param p The pair to insert.
   1.196 +    void push(const Pair &p) {
   1.197 +      int n = data.size();
   1.198 +      data.resize(n+1);
   1.199 +      bubble_up(n, p);
   1.200 +    }
   1.201 +
   1.202 +    /// \brief Insert an item into the heap with the given heap.
   1.203 +    ///
   1.204 +    /// Adds \c i to the heap with priority \c p.
   1.205 +    /// \param i The item to insert.
   1.206 +    /// \param p The priority of the item.
   1.207 +    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
   1.208 +
   1.209 +    /// \brief Returns the item with minimum priority relative to \c Compare.
   1.210 +    ///
   1.211 +    /// This method returns the item with minimum priority relative to \c
   1.212 +    /// Compare.
   1.213 +    /// \pre The heap must be nonempty.
   1.214 +    Item top() const { return data[0].first; }
   1.215 +
   1.216 +    /// \brief Returns the minimum priority relative to \c Compare.
   1.217 +    ///
   1.218 +    /// It returns the minimum priority relative to \c Compare.
   1.219 +    /// \pre The heap must be nonempty.
   1.220 +    Prio prio() const { return data[0].second; }
   1.221 +
   1.222 +    /// \brief Deletes the item with minimum priority relative to \c Compare.
   1.223 +    ///
   1.224 +    /// This method deletes the item with minimum priority relative to \c
   1.225 +    /// Compare from the heap.
   1.226 +    /// \pre The heap must be non-empty.
   1.227 +    void pop() {
   1.228 +      int n = data.size()-1;
   1.229 +      iim.set(data[0].first, POST_HEAP);
   1.230 +      if (n>0) bubble_down(0, data[n], n);
   1.231 +      data.pop_back();
   1.232 +    }
   1.233 +
   1.234 +    /// \brief Deletes \c i from the heap.
   1.235 +    ///
   1.236 +    /// This method deletes item \c i from the heap.
   1.237 +    /// \param i The item to erase.
   1.238 +    /// \pre The item should be in the heap.
   1.239 +    void erase(const Item &i) {
   1.240 +      int h = iim[i];
   1.241 +      int n = data.size()-1;
   1.242 +      iim.set(data[h].first, POST_HEAP);
   1.243 +      if( h<n ) {
   1.244 +        if( less(data[parent(h)], data[n]) )
   1.245 +          bubble_down(h, data[n], n);
   1.246 +        else
   1.247 +          bubble_up(h, data[n]);
   1.248 +      }
   1.249 +      data.pop_back();
   1.250 +    }
   1.251 +
   1.252 +    /// \brief Returns the priority of \c i.
   1.253 +    ///
   1.254 +    /// This function returns the priority of item \c i.
   1.255 +    /// \pre \c i must be in the heap.
   1.256 +    /// \param i The item.
   1.257 +    Prio operator[](const Item &i) const {
   1.258 +      int idx = iim[i];
   1.259 +      return data[idx].second;
   1.260 +    }
   1.261 +
   1.262 +    /// \brief \c i gets to the heap with priority \c p independently
   1.263 +    /// if \c i was already there.
   1.264 +    ///
   1.265 +    /// This method calls \ref push(\c i, \c p) if \c i is not stored
   1.266 +    /// in the heap and sets the priority of \c i to \c p otherwise.
   1.267 +    /// \param i The item.
   1.268 +    /// \param p The priority.
   1.269 +    void set(const Item &i, const Prio &p) {
   1.270 +      int idx = iim[i];
   1.271 +      if( idx < 0 )
   1.272 +        push(i,p);
   1.273 +      else if( comp(p, data[idx].second) )
   1.274 +        bubble_up(idx, Pair(i,p));
   1.275 +      else
   1.276 +        bubble_down(idx, Pair(i,p), data.size());
   1.277 +    }
   1.278 +
   1.279 +    /// \brief Decreases the priority of \c i to \c p.
   1.280 +    ///
   1.281 +    /// This method decreases the priority of item \c i to \c p.
   1.282 +    /// \pre \c i must be stored in the heap with priority at least \c
   1.283 +    /// p relative to \c Compare.
   1.284 +    /// \param i The item.
   1.285 +    /// \param p The priority.
   1.286 +    void decrease(const Item &i, const Prio &p) {
   1.287 +      int idx = iim[i];
   1.288 +      bubble_up(idx, Pair(i,p));
   1.289 +    }
   1.290 +
   1.291 +    /// \brief Increases the priority of \c i to \c p.
   1.292 +    ///
   1.293 +    /// This method sets the priority of item \c i to \c p.
   1.294 +    /// \pre \c i must be stored in the heap with priority at most \c
   1.295 +    /// p relative to \c Compare.
   1.296 +    /// \param i The item.
   1.297 +    /// \param p The priority.
   1.298 +    void increase(const Item &i, const Prio &p) {
   1.299 +      int idx = iim[i];
   1.300 +      bubble_down(idx, Pair(i,p), data.size());
   1.301 +    }
   1.302 +
   1.303 +    /// \brief Returns if \c item is in, has already been in, or has
   1.304 +    /// never been in the heap.
   1.305 +    ///
   1.306 +    /// This method returns PRE_HEAP if \c item has never been in the
   1.307 +    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   1.308 +    /// otherwise. In the latter case it is possible that \c item will
   1.309 +    /// get back to the heap again.
   1.310 +    /// \param i The item.
   1.311 +    State state(const Item &i) const {
   1.312 +      int s = iim[i];
   1.313 +      if (s>=0) s=0;
   1.314 +      return State(s);
   1.315 +    }
   1.316 +
   1.317 +    /// \brief Sets the state of the \c item in the heap.
   1.318 +    ///
   1.319 +    /// Sets the state of the \c item in the heap. It can be used to
   1.320 +    /// manually clear the heap when it is important to achive the
   1.321 +    /// better time complexity.
   1.322 +    /// \param i The item.
   1.323 +    /// \param st The state. It should not be \c IN_HEAP.
   1.324 +    void state(const Item& i, State st) {
   1.325 +      switch (st) {
   1.326 +        case POST_HEAP:
   1.327 +        case PRE_HEAP:
   1.328 +          if (state(i) == IN_HEAP) erase(i);
   1.329 +          iim[i] = st;
   1.330 +          break;
   1.331 +        case IN_HEAP:
   1.332 +          break;
   1.333 +      }
   1.334 +    }
   1.335 +
   1.336 +    /// \brief Replaces an item in the heap.
   1.337 +    ///
   1.338 +    /// The \c i item is replaced with \c j item. The \c i item should
   1.339 +    /// be in the heap, while the \c j should be out of the heap. The
   1.340 +    /// \c i item will out of the heap and \c j will be in the heap
   1.341 +    /// with the same prioriority as prevoiusly the \c i item.
   1.342 +    void replace(const Item& i, const Item& j) {
   1.343 +      int idx = iim[i];
   1.344 +      iim.set(i, iim[j]);
   1.345 +      iim.set(j, idx);
   1.346 +      data[idx].first = j;
   1.347 +    }
   1.348 +
   1.349 +  }; // class FouraryHeap
   1.350 +
   1.351 +} // namespace lemon
   1.352 +
   1.353 +#endif // LEMON_FOURARY_HEAP_H