1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dheap.h Tue Sep 29 13:32:01 2009 +0200
1.3 @@ -0,0 +1,352 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
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_DHEAP_H
1.23 +#define LEMON_DHEAP_H
1.24 +
1.25 +///\ingroup heaps
1.26 +///\file
1.27 +///\brief D-ary heap implementation.
1.28 +
1.29 +#include <vector>
1.30 +#include <utility>
1.31 +#include <functional>
1.32 +
1.33 +namespace lemon {
1.34 +
1.35 + /// \ingroup heaps
1.36 + ///
1.37 + ///\brief D-ary heap data structure.
1.38 + ///
1.39 + /// This class implements the \e D-ary \e heap data structure.
1.40 + /// It fully conforms to the \ref concepts::Heap "heap concept".
1.41 + ///
1.42 + /// The \ref DHeap "D-ary heap" is a generalization of the
1.43 + /// \ref BinHeap "binary heap" structure, its nodes have at most
1.44 + /// \c D children, instead of two.
1.45 + /// \ref BinHeap and \ref QuadHeap are specialized implementations
1.46 + /// of this structure for <tt>D=2</tt> and <tt>D=4</tt>, respectively.
1.47 + ///
1.48 + /// \tparam PR Type of the priorities of the items.
1.49 + /// \tparam IM A read-writable item map with \c int values, used
1.50 + /// internally to handle the cross references.
1.51 + /// \tparam D The degree of the heap, each node have at most \e D
1.52 + /// children. The default is 16. Powers of two are suggested to use
1.53 + /// so that the multiplications and divisions needed to traverse the
1.54 + /// nodes of the heap could be performed faster.
1.55 + /// \tparam CMP A functor class for comparing the priorities.
1.56 + /// The default is \c std::less<PR>.
1.57 + ///
1.58 + ///\sa BinHeap
1.59 + ///\sa FouraryHeap
1.60 +#ifdef DOXYGEN
1.61 + template <typename PR, typename IM, int D, typename CMP>
1.62 +#else
1.63 + template <typename PR, typename IM, int D = 16,
1.64 + typename CMP = std::less<PR> >
1.65 +#endif
1.66 + class DHeap {
1.67 + public:
1.68 + /// Type of the item-int map.
1.69 + typedef IM ItemIntMap;
1.70 + /// Type of the priorities.
1.71 + typedef PR Prio;
1.72 + /// Type of the items stored in the heap.
1.73 + typedef typename ItemIntMap::Key Item;
1.74 + /// Type of the item-priority pairs.
1.75 + typedef std::pair<Item,Prio> Pair;
1.76 + /// Functor type for comparing the priorities.
1.77 + typedef CMP Compare;
1.78 +
1.79 + /// \brief Type to represent the states of the items.
1.80 + ///
1.81 + /// Each item has a state associated to it. It can be "in heap",
1.82 + /// "pre-heap" or "post-heap". The latter two are indifferent from the
1.83 + /// heap's point of view, but may be useful to the user.
1.84 + ///
1.85 + /// The item-int map must be initialized in such way that it assigns
1.86 + /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
1.87 + enum State {
1.88 + IN_HEAP = 0, ///< = 0.
1.89 + PRE_HEAP = -1, ///< = -1.
1.90 + POST_HEAP = -2 ///< = -2.
1.91 + };
1.92 +
1.93 + private:
1.94 + std::vector<Pair> _data;
1.95 + Compare _comp;
1.96 + ItemIntMap &_iim;
1.97 +
1.98 + public:
1.99 + /// \brief Constructor.
1.100 + ///
1.101 + /// Constructor.
1.102 + /// \param map A map that assigns \c int values to the items.
1.103 + /// It is used internally to handle the cross references.
1.104 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.105 + explicit DHeap(ItemIntMap &map) : _iim(map) {}
1.106 +
1.107 + /// \brief Constructor.
1.108 + ///
1.109 + /// Constructor.
1.110 + /// \param map A map that assigns \c int values to the items.
1.111 + /// It is used internally to handle the cross references.
1.112 + /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
1.113 + /// \param comp The function object used for comparing the priorities.
1.114 + DHeap(ItemIntMap &map, const Compare &comp)
1.115 + : _iim(map), _comp(comp) {}
1.116 +
1.117 + /// \brief The number of items stored in the heap.
1.118 + ///
1.119 + /// This function returns the number of items stored in the heap.
1.120 + int size() const { return _data.size(); }
1.121 +
1.122 + /// \brief Check if the heap is empty.
1.123 + ///
1.124 + /// This function returns \c true if the heap is empty.
1.125 + bool empty() const { return _data.empty(); }
1.126 +
1.127 + /// \brief Make the heap empty.
1.128 + ///
1.129 + /// This functon makes the heap empty.
1.130 + /// It does not change the cross reference map. If you want to reuse
1.131 + /// a heap that is not surely empty, you should first clear it and
1.132 + /// then you should set the cross reference map to \c PRE_HEAP
1.133 + /// for each item.
1.134 + void clear() { _data.clear(); }
1.135 +
1.136 + private:
1.137 + int parent(int i) { return (i-1)/D; }
1.138 + int firstChild(int i) { return D*i+1; }
1.139 +
1.140 + bool less(const Pair &p1, const Pair &p2) const {
1.141 + return _comp(p1.second, p2.second);
1.142 + }
1.143 +
1.144 + void bubbleUp(int hole, Pair p) {
1.145 + int par = parent(hole);
1.146 + while( hole>0 && less(p,_data[par]) ) {
1.147 + move(_data[par],hole);
1.148 + hole = par;
1.149 + par = parent(hole);
1.150 + }
1.151 + move(p, hole);
1.152 + }
1.153 +
1.154 + void bubbleDown(int hole, Pair p, int length) {
1.155 + if( length>1 ) {
1.156 + int child = firstChild(hole);
1.157 + while( child+D<=length ) {
1.158 + int min=child;
1.159 + for (int i=1; i<D; ++i) {
1.160 + if( less(_data[child+i], _data[min]) )
1.161 + min=child+i;
1.162 + }
1.163 + if( !less(_data[min], p) )
1.164 + goto ok;
1.165 + move(_data[min], hole);
1.166 + hole = min;
1.167 + child = firstChild(hole);
1.168 + }
1.169 + if ( child<length ) {
1.170 + int min = child;
1.171 + while (++child < length) {
1.172 + if( less(_data[child], _data[min]) )
1.173 + min=child;
1.174 + }
1.175 + if( less(_data[min], p) ) {
1.176 + move(_data[min], hole);
1.177 + hole = min;
1.178 + }
1.179 + }
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 + /// \brief Insert a pair of item and priority into the heap.
1.192 + ///
1.193 + /// This function inserts \c p.first to the heap with priority
1.194 + /// \c p.second.
1.195 + /// \param p The pair to insert.
1.196 + /// \pre \c p.first must not be stored in the heap.
1.197 + void push(const Pair &p) {
1.198 + int n = _data.size();
1.199 + _data.resize(n+1);
1.200 + bubbleUp(n, p);
1.201 + }
1.202 +
1.203 + /// \brief Insert an item into the heap with the given priority.
1.204 + ///
1.205 + /// This function inserts the given item into the heap with the
1.206 + /// given priority.
1.207 + /// \param i The item to insert.
1.208 + /// \param p The priority of the item.
1.209 + /// \pre \e i must not be stored in the heap.
1.210 + void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
1.211 +
1.212 + /// \brief Return the item having minimum priority.
1.213 + ///
1.214 + /// This function returns the item having minimum priority.
1.215 + /// \pre The heap must be non-empty.
1.216 + Item top() const { return _data[0].first; }
1.217 +
1.218 + /// \brief The minimum priority.
1.219 + ///
1.220 + /// This function returns the minimum priority.
1.221 + /// \pre The heap must be non-empty.
1.222 + Prio prio() const { return _data[0].second; }
1.223 +
1.224 + /// \brief Remove the item having minimum priority.
1.225 + ///
1.226 + /// This function removes the item having minimum priority.
1.227 + /// \pre The heap must be non-empty.
1.228 + void pop() {
1.229 + int n = _data.size()-1;
1.230 + _iim.set(_data[0].first, POST_HEAP);
1.231 + if (n>0) bubbleDown(0, _data[n], n);
1.232 + _data.pop_back();
1.233 + }
1.234 +
1.235 + /// \brief Remove the given item from the heap.
1.236 + ///
1.237 + /// This function removes the given item from the heap if it is
1.238 + /// already stored.
1.239 + /// \param i The item to delete.
1.240 + /// \pre \e i must be in the heap.
1.241 + void erase(const Item &i) {
1.242 + int h = _iim[i];
1.243 + int n = _data.size()-1;
1.244 + _iim.set(_data[h].first, POST_HEAP);
1.245 + if( h<n ) {
1.246 + if( less(_data[parent(h)], _data[n]) )
1.247 + bubbleDown(h, _data[n], n);
1.248 + else
1.249 + bubbleUp(h, _data[n]);
1.250 + }
1.251 + _data.pop_back();
1.252 + }
1.253 +
1.254 + /// \brief The priority of the given item.
1.255 + ///
1.256 + /// This function returns the priority of the given item.
1.257 + /// \param i The item.
1.258 + /// \pre \e i must be in the heap.
1.259 + Prio operator[](const Item &i) const {
1.260 + int idx = _iim[i];
1.261 + return _data[idx].second;
1.262 + }
1.263 +
1.264 + /// \brief Set the priority of an item or insert it, if it is
1.265 + /// not stored in the heap.
1.266 + ///
1.267 + /// This method sets the priority of the given item if it is
1.268 + /// already stored in the heap. Otherwise it inserts the given
1.269 + /// item into the heap with the given priority.
1.270 + /// \param i The item.
1.271 + /// \param p The priority.
1.272 + void set(const Item &i, const Prio &p) {
1.273 + int idx = _iim[i];
1.274 + if( idx<0 )
1.275 + push(i,p);
1.276 + else if( _comp(p, _data[idx].second) )
1.277 + bubbleUp(idx, Pair(i,p));
1.278 + else
1.279 + bubbleDown(idx, Pair(i,p), _data.size());
1.280 + }
1.281 +
1.282 + /// \brief Decrease the priority of an item to the given value.
1.283 + ///
1.284 + /// This function decreases the priority of an item to the given value.
1.285 + /// \param i The item.
1.286 + /// \param p The priority.
1.287 + /// \pre \e i must be stored in the heap with priority at least \e p.
1.288 + void decrease(const Item &i, const Prio &p) {
1.289 + int idx = _iim[i];
1.290 + bubbleUp(idx, Pair(i,p));
1.291 + }
1.292 +
1.293 + /// \brief Increase the priority of an item to the given value.
1.294 + ///
1.295 + /// This function increases the priority of an item to the given value.
1.296 + /// \param i The item.
1.297 + /// \param p The priority.
1.298 + /// \pre \e i must be stored in the heap with priority at most \e p.
1.299 + void increase(const Item &i, const Prio &p) {
1.300 + int idx = _iim[i];
1.301 + bubbleDown(idx, Pair(i,p), _data.size());
1.302 + }
1.303 +
1.304 + /// \brief Return the state of an item.
1.305 + ///
1.306 + /// This method returns \c PRE_HEAP if the given item has never
1.307 + /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
1.308 + /// and \c POST_HEAP otherwise.
1.309 + /// In the latter case it is possible that the item will get back
1.310 + /// to the heap again.
1.311 + /// \param i The item.
1.312 + State state(const Item &i) const {
1.313 + int s = _iim[i];
1.314 + if (s>=0) s=0;
1.315 + return State(s);
1.316 + }
1.317 +
1.318 + /// \brief Set the state of an item in the heap.
1.319 + ///
1.320 + /// This function sets the state of the given item in the heap.
1.321 + /// It can be used to manually clear the heap when it is important
1.322 + /// to achive better time complexity.
1.323 + /// \param i The item.
1.324 + /// \param st The state. It should not be \c IN_HEAP.
1.325 + void state(const Item& i, State st) {
1.326 + switch (st) {
1.327 + case POST_HEAP:
1.328 + case PRE_HEAP:
1.329 + if (state(i) == IN_HEAP) erase(i);
1.330 + _iim[i] = st;
1.331 + break;
1.332 + case IN_HEAP:
1.333 + break;
1.334 + }
1.335 + }
1.336 +
1.337 + /// \brief Replace an item in the heap.
1.338 + ///
1.339 + /// This function replaces item \c i with item \c j.
1.340 + /// Item \c i must be in the heap, while \c j must be out of the heap.
1.341 + /// After calling this method, item \c i will be out of the
1.342 + /// heap and \c j will be in the heap with the same prioriority
1.343 + /// as item \c i had before.
1.344 + void replace(const Item& i, const Item& j) {
1.345 + int idx=_iim[i];
1.346 + _iim.set(i, _iim[j]);
1.347 + _iim.set(j, idx);
1.348 + _data[idx].first=j;
1.349 + }
1.350 +
1.351 + }; // class DHeap
1.352 +
1.353 +} // namespace lemon
1.354 +
1.355 +#endif // LEMON_DHEAP_H