Changeset 750:bb3392fe91f2 in lemon for lemon/kary_heap.h
- Timestamp:
- 07/09/09 04:07:08 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/kary_heap.h
r748 r750 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-200 81 /* -*- 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 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #define LEMON_KARY_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Kary Heap implementation. 25 26 #include <iostream> 24 ///\brief Fourary heap implementation. 25 27 26 #include <vector> 28 27 #include <utility> … … 31 30 namespace lemon { 32 31 33 ///\ingroup auxdat 34 /// 35 ///\brief A Kary Heap implementation. 36 /// 37 ///This class implements the \e Kary \e heap data structure. A \e heap 38 ///is a data structure for storing items with specified values called \e 39 ///priorities in such a way that finding the item with minimum priority is 40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 41 ///one can change the priority of an item, add or erase an item, etc. 42 /// 43 ///\param _Prio Type of the priority of the items. 44 ///\param _ItemIntMap A read and writable Item int map, used internally 45 ///to handle the cross references. 46 ///\param _Compare A class for the ordering of the priorities. The 47 ///default is \c std::less<_Prio>. 48 /// 49 ///\sa FibHeap 50 ///\sa Dijkstra 51 ///\author Dorian Batha 52 53 template <typename _Prio, typename _ItemIntMap, 54 typename _Compare = std::less<_Prio> > 55 32 /// \ingroup heaps 33 /// 34 ///\brief K-ary heap data structure. 35 /// 36 /// This class implements the \e K-ary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 38 /// 39 /// The \ref KaryHeap "K-ary heap" is a generalization of the 40 /// \ref BinHeap "binary heap" structure, its nodes have at most 41 /// \c K children, instead of two. 42 /// \ref BinHeap and \ref FouraryHeap are specialized implementations 43 /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively. 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 /// 51 ///\sa BinHeap 52 ///\sa FouraryHeap 53 #ifdef DOXYGEN 54 template <typename PR, typename IM, typename CMP> 55 #else 56 template <typename PR, typename IM, typename CMP = std::less<PR> > 57 #endif 56 58 class KaryHeap { 57 58 59 public: 59 /// \e60 typedef _ItemIntMapItemIntMap;61 /// \e62 typedef _PrioPrio;63 /// \e60 /// Type of the item-int map. 61 typedef IM ItemIntMap; 62 /// Type of the priorities. 63 typedef PR Prio; 64 /// Type of the items stored in the heap. 64 65 typedef typename ItemIntMap::Key Item; 65 /// \e66 /// Type of the item-priority pairs. 66 67 typedef std::pair<Item,Prio> Pair; 67 ///\e 68 typedef _Compare Compare; 69 ///\e 70 71 /// \brief Type to represent the items states. 72 /// 73 /// Each Item element have a state associated to it. It may be "in heap", 74 /// "pre heap" or "post heap". The latter two are indifferent from the 68 /// Functor type for comparing the priorities. 69 typedef CMP Compare; 70 71 /// \brief Type to represent the states of the items. 72 /// 73 /// Each item has a state associated to it. It can be "in heap", 74 /// "pre-heap" or "post-heap". The latter two are indifferent from the 75 75 /// heap's point of view, but may be useful to the user. 76 76 /// 77 /// The ItemIntMap \e should be initialized in such way that it maps78 /// PRE_HEAP (-1) to any element to be put in the heap...77 /// The item-int map must be initialized in such way that it assigns 78 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 79 79 enum State { 80 IN_HEAP = 0, 81 PRE_HEAP = -1, 82 POST_HEAP = -2 80 IN_HEAP = 0, ///< = 0. 81 PRE_HEAP = -1, ///< = -1. 82 POST_HEAP = -2 ///< = -2. 83 83 }; 84 84 85 85 private: 86 std::vector<Pair> data;87 Compare comp;88 ItemIntMap & iim;89 int K;86 std::vector<Pair> _data; 87 Compare _comp; 88 ItemIntMap &_iim; 89 int _K; 90 90 91 91 public: 92 /// \brief The constructor. 93 /// 94 /// The constructor. 95 /// \param _iim should be given to the constructor, since it is used 96 /// internally to handle the cross references. The value of the map 97 /// should be PRE_HEAP (-1) for each element. 98 explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {} 99 100 /// \brief The constructor. 101 /// 102 /// The constructor. 103 /// \param _iim should be given to the constructor, since it is used 104 /// internally to handle the cross references. The value of the map 105 /// should be PRE_HEAP (-1) for each element. 106 /// 107 /// \param _comp The comparator function object. 108 KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32) 109 : iim(_iim), comp(_comp), K(_K) {} 110 111 112 /// The number of items stored in the heap. 113 /// 114 /// \brief Returns the number of items stored in the heap. 115 int size() const { return data.size(); } 116 117 /// \brief Checks if the heap stores no items. 118 /// 119 /// Returns \c true if and only if the heap stores no items. 120 bool empty() const { return data.empty(); } 121 122 /// \brief Make empty this heap. 123 /// 124 /// Make empty this heap. It does not change the cross reference map. 125 /// If you want to reuse what is not surely empty you should first clear 126 /// the heap and after that you should set the cross reference map for 127 /// each item to \c PRE_HEAP. 128 void clear() { data.clear(); } 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 explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {} 99 100 /// \brief Constructor. 101 /// 102 /// Constructor. 103 /// \param map A map that assigns \c int values to the items. 104 /// It is used internally to handle the cross references. 105 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 106 /// \param comp The function object used for comparing the priorities. 107 KaryHeap(ItemIntMap &map, const Compare &comp, int K=32) 108 : _iim(map), _comp(comp), _K(K) {} 109 110 /// \brief The number of items stored in the heap. 111 /// 112 /// This function returns the number of items stored in the heap. 113 int size() const { return _data.size(); } 114 115 /// \brief Check if the heap is empty. 116 /// 117 /// This function returns \c true if the heap is empty. 118 bool empty() const { return _data.empty(); } 119 120 /// \brief Make the heap empty. 121 /// 122 /// This functon makes the heap empty. 123 /// It does not change the cross reference map. If you want to reuse 124 /// a heap that is not surely empty, you should first clear it and 125 /// then you should set the cross reference map to \c PRE_HEAP 126 /// for each item. 127 void clear() { _data.clear(); } 129 128 130 129 private: 131 int parent(int i) { return (i-1)/ K; }132 int first _child(int i) { returnK*i+1; }130 int parent(int i) { return (i-1)/_K; } 131 int firstChild(int i) { return _K*i+1; } 133 132 134 133 bool less(const Pair &p1, const Pair &p2) const { 135 return comp(p1.second, p2.second);136 } 137 138 int find _min(const int child, const int length) {134 return _comp(p1.second, p2.second); 135 } 136 137 int findMin(const int child, const int length) { 139 138 int min=child, i=1; 140 while( i< K && child+i<length ) {141 if( less( data[child+i],data[min]) )139 while( i<_K && child+i<length ) { 140 if( less(_data[child+i], _data[min]) ) 142 141 min=child+i; 143 142 ++i; … … 146 145 } 147 146 148 void bubble _up(int hole, Pair p) {147 void bubbleUp(int hole, Pair p) { 149 148 int par = parent(hole); 150 while( hole>0 && less(p, data[par]) ) {151 move( data[par],hole);149 while( hole>0 && less(p,_data[par]) ) { 150 move(_data[par],hole); 152 151 hole = par; 153 152 par = parent(hole); … … 156 155 } 157 156 158 void bubble _down(int hole, Pair p, int length) {157 void bubbleDown(int hole, Pair p, int length) { 159 158 if( length>1 ) { 160 int child = first _child(hole);159 int child = firstChild(hole); 161 160 while( child<length ) { 162 child = find _min(child, length);163 if( !less( data[child], p) )161 child = findMin(child, length); 162 if( !less(_data[child], p) ) 164 163 goto ok; 165 move( data[child], hole);164 move(_data[child], hole); 166 165 hole = child; 167 child = first _child(hole);166 child = firstChild(hole); 168 167 } 169 168 } … … 173 172 174 173 void move(const Pair &p, int i) { 175 data[i] = p;176 iim.set(p.first, i);174 _data[i] = p; 175 _iim.set(p.first, i); 177 176 } 178 177 … … 180 179 /// \brief Insert a pair of item and priority into the heap. 181 180 /// 182 /// Adds \c p.first to the heap with priority \c p.second. 181 /// This function inserts \c p.first to the heap with priority 182 /// \c p.second. 183 183 /// \param p The pair to insert. 184 /// \pre \c p.first must not be stored in the heap. 184 185 void push(const Pair &p) { 185 int n = data.size(); 186 data.resize(n+1); 187 bubble_up(n, p); 188 } 189 190 /// \brief Insert an item into the heap with the given heap. 191 /// 192 /// Adds \c i to the heap with priority \c p. 186 int n = _data.size(); 187 _data.resize(n+1); 188 bubbleUp(n, p); 189 } 190 191 /// \brief Insert an item into the heap with the given priority. 192 /// 193 /// This function inserts the given item into the heap with the 194 /// given priority. 193 195 /// \param i The item to insert. 194 196 /// \param p The priority of the item. 197 /// \pre \e i must not be stored in the heap. 195 198 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 196 199 197 /// \brief Returns the item with minimum priority relative to \c Compare. 198 /// 199 /// This method returns the item with minimum priority relative to \c 200 /// Compare. 201 /// \pre The heap must be nonempty. 202 Item top() const { return data[0].first; } 203 204 /// \brief Returns the minimum priority relative to \c Compare. 205 /// 206 /// It returns the minimum priority relative to \c Compare. 207 /// \pre The heap must be nonempty. 208 Prio prio() const { return data[0].second; } 209 210 /// \brief Deletes the item with minimum priority relative to \c Compare. 211 /// 212 /// This method deletes the item with minimum priority relative to \c 213 /// Compare from the heap. 200 /// \brief Return the item having minimum priority. 201 /// 202 /// This function returns the item having minimum priority. 203 /// \pre The heap must be non-empty. 204 Item top() const { return _data[0].first; } 205 206 /// \brief The minimum priority. 207 /// 208 /// This function returns the minimum priority. 209 /// \pre The heap must be non-empty. 210 Prio prio() const { return _data[0].second; } 211 212 /// \brief Remove the item having minimum priority. 213 /// 214 /// This function removes the item having minimum priority. 214 215 /// \pre The heap must be non-empty. 215 216 void pop() { 216 int n = data.size()-1; 217 iim.set(data[0].first, POST_HEAP); 218 if (n>0) bubble_down(0, data[n], n); 219 data.pop_back(); 220 } 221 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. 217 int n = _data.size()-1; 218 _iim.set(_data[0].first, POST_HEAP); 219 if (n>0) bubbleDown(0, _data[n], n); 220 _data.pop_back(); 221 } 222 223 /// \brief Remove the given item from the heap. 224 /// 225 /// This function removes the given item from the heap if it is 226 /// already stored. 227 /// \param i The item to delete. 228 /// \pre \e i must be in the heap. 227 229 void erase(const Item &i) { 228 int h = iim[i];229 int n = data.size()-1;230 iim.set(data[h].first, POST_HEAP);230 int h = _iim[i]; 231 int n = _data.size()-1; 232 _iim.set(_data[h].first, POST_HEAP); 231 233 if( h<n ) { 232 if( less( data[parent(h)],data[n]) )233 bubble _down(h,data[n], n);234 if( less(_data[parent(h)], _data[n]) ) 235 bubbleDown(h, _data[n], n); 234 236 else 235 bubble_up(h, data[n]); 236 } 237 data.pop_back(); 238 } 239 240 241 /// \brief Returns the priority of \c i. 242 /// 243 /// This function returns the priority of item \c i. 244 /// \pre \c i must be in the heap. 245 /// \param i The item. 237 bubbleUp(h, _data[n]); 238 } 239 _data.pop_back(); 240 } 241 242 /// \brief The priority of the given item. 243 /// 244 /// This function returns the priority of the given item. 245 /// \param i The item. 246 /// \pre \e i must be in the heap. 246 247 Prio operator[](const Item &i) const { 247 int idx = iim[i]; 248 return data[idx].second; 249 } 250 251 /// \brief \c i gets to the heap with priority \c p independently 252 /// if \c i was already there. 253 /// 254 /// This method calls \ref push(\c i, \c p) if \c i is not stored 255 /// in the heap and sets the priority of \c i to \c p otherwise. 248 int idx = _iim[i]; 249 return _data[idx].second; 250 } 251 252 /// \brief Set the priority of an item or insert it, if it is 253 /// not stored in the heap. 254 /// 255 /// This method sets the priority of the given item if it is 256 /// already stored in the heap. Otherwise it inserts the given 257 /// item into the heap with the given priority. 256 258 /// \param i The item. 257 259 /// \param p The priority. 258 260 void set(const Item &i, const Prio &p) { 259 int idx = iim[i];261 int idx = _iim[i]; 260 262 if( idx<0 ) 261 263 push(i,p); 262 else if( comp(p,data[idx].second) )263 bubble _up(idx, Pair(i,p));264 else if( _comp(p, _data[idx].second) ) 265 bubbleUp(idx, Pair(i,p)); 264 266 else 265 bubble_down(idx, Pair(i,p), data.size()); 266 } 267 268 /// \brief Decreases the priority of \c i to \c p. 269 /// 270 /// This method decreases the priority of item \c i to \c p. 271 /// \pre \c i must be stored in the heap with priority at least \c 272 /// p relative to \c Compare. 267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 270 /// \brief Decrease the priority of an item to the given value. 271 /// 272 /// This function decreases the priority of an item to the given value. 273 273 /// \param i The item. 274 274 /// \param p The priority. 275 /// \pre \e i must be stored in the heap with priority at least \e p. 275 276 void decrease(const Item &i, const Prio &p) { 276 int idx = iim[i]; 277 bubble_up(idx, Pair(i,p)); 278 } 279 280 /// \brief Increases the priority of \c i to \c p. 281 /// 282 /// This method sets the priority of item \c i to \c p. 283 /// \pre \c i must be stored in the heap with priority at most \c 284 /// p relative to \c Compare. 277 int idx = _iim[i]; 278 bubbleUp(idx, Pair(i,p)); 279 } 280 281 /// \brief Increase the priority of an item to the given value. 282 /// 283 /// This function increases the priority of an item to the given value. 285 284 /// \param i The item. 286 285 /// \param p The priority. 286 /// \pre \e i must be stored in the heap with priority at most \e p. 287 287 void increase(const Item &i, const Prio &p) { 288 int idx = iim[i];289 bubble _down(idx, Pair(i,p),data.size());290 } 291 292 /// \brief Return s if \c item is in, has already been in, or has293 /// never been in the heap.294 /// 295 /// This method returns PRE_HEAP if \c item has never been in the296 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP297 /// otherwise. In the latter case it is possible that \c item will298 /// get backto the heap again.288 int idx = _iim[i]; 289 bubbleDown(idx, Pair(i,p), _data.size()); 290 } 291 292 /// \brief Return the state of an item. 293 /// 294 /// This method returns \c PRE_HEAP if the given item has never 295 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 296 /// and \c POST_HEAP otherwise. 297 /// In the latter case it is possible that the item will get back 298 /// to the heap again. 299 299 /// \param i The item. 300 300 State state(const Item &i) const { 301 int s = iim[i];301 int s = _iim[i]; 302 302 if (s>=0) s=0; 303 303 return State(s); 304 304 } 305 305 306 /// \brief Set s the state of the \citem in the heap.307 /// 308 /// Sets the state of the \c item in the heap. It can be used to309 /// manually clear the heap when it is important to achive the310 /// better time complexity.306 /// \brief Set the state of an item in the heap. 307 /// 308 /// This function sets the state of the given item in the heap. 309 /// It can be used to manually clear the heap when it is important 310 /// to achive better time complexity. 311 311 /// \param i The item. 312 312 /// \param st The state. It should not be \c IN_HEAP. 313 313 void state(const Item& i, State st) { 314 314 switch (st) { 315 case POST_HEAP: 316 case PRE_HEAP: 317 if (state(i) == IN_HEAP) erase(i); 318 iim[i] = st; 319 break; 320 case IN_HEAP: 321 break; 322 } 323 } 324 325 /// \brief Replaces an item in the heap. 326 /// 327 /// The \c i item is replaced with \c j item. The \c i item should 328 /// be in the heap, while the \c j should be out of the heap. The 329 /// \c i item will out of the heap and \c j will be in the heap 330 /// with the same prioriority as prevoiusly the \c i item. 315 case POST_HEAP: 316 case PRE_HEAP: 317 if (state(i) == IN_HEAP) erase(i); 318 _iim[i] = st; 319 break; 320 case IN_HEAP: 321 break; 322 } 323 } 324 325 /// \brief Replace an item in the heap. 326 /// 327 /// This function replaces item \c i with item \c j. 328 /// Item \c i must be in the heap, while \c j must be out of the heap. 329 /// After calling this method, item \c i will be out of the 330 /// heap and \c j will be in the heap with the same prioriority 331 /// as item \c i had before. 331 332 void replace(const Item& i, const Item& j) { 332 int idx= iim[i];333 iim.set(i,iim[j]);334 iim.set(j, idx);335 data[idx].first=j;333 int idx=_iim[i]; 334 _iim.set(i, _iim[j]); 335 _iim.set(j, idx); 336 _data[idx].first=j; 336 337 } 337 338
Note: See TracChangeset
for help on using the changeset viewer.