Changeset 606:c5fd2d996909 in lemon for lemon/bin_heap.h
 Timestamp:
 03/29/09 23:08:20 (14 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bin_heap.h
r463 r606 34 34 ///\brief A Binary Heap implementation. 35 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. 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 Comp 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. 41 43 /// 42 ///\tparam _PrioType of the priority of the items.43 ///\tparam _ItemIntMap A read and writable Item int map, used internally44 ///\tparam PR Type of the priority of the items. 45 ///\tparam IM A read and writable item map with int values, used internally 44 46 ///to handle the cross references. 45 ///\tparam _Compare A class for the ordering of the priorities. The46 /// default is \c std::less<_Prio>.47 ///\tparam Comp A functor class for the ordering of the priorities. 48 ///The default is \c std::less<PR>. 47 49 /// 48 50 ///\sa FibHeap 49 51 ///\sa Dijkstra 50 template <typename _Prio, typename _ItemIntMap, 51 typename _Compare = std::less<_Prio> > 52 template <typename PR, typename IM, typename Comp = std::less<PR> > 52 53 class BinHeap { 53 54 54 55 public: 55 56 ///\e 56 typedef _ItemIntMapItemIntMap;57 ///\e 58 typedef _PrioPrio;57 typedef IM ItemIntMap; 58 ///\e 59 typedef PR Prio; 59 60 ///\e 60 61 typedef typename ItemIntMap::Key Item; … … 62 63 typedef std::pair<Item,Prio> Pair; 63 64 ///\e 64 typedef _CompareCompare;65 typedef Comp Compare; 65 66 66 67 /// \brief Type to represent the items states. … … 70 71 /// heap's point of view, but may be useful to the user. 71 72 /// 72 /// The ItemIntMap \e should be initialized in such way that it maps73 /// PRE_HEAP (1) to any element to be put in the heap...73 /// The itemint map must be initialized in such way that it assigns 74 /// \c PRE_HEAP (<tt>1</tt>) to any element to be put in the heap. 74 75 enum State { 75 IN_HEAP = 0, 76 PRE_HEAP = 1, 77 POST_HEAP = 2 76 IN_HEAP = 0, ///< \e 77 PRE_HEAP = 1, ///< \e 78 POST_HEAP = 2 ///< \e 78 79 }; 79 80 80 81 private: 81 std::vector<Pair> data;82 Compare comp;83 ItemIntMap & iim;82 std::vector<Pair> _data; 83 Compare _comp; 84 ItemIntMap &_iim; 84 85 85 86 public: … … 87 88 /// 88 89 /// The constructor. 89 /// \param _iim should be given to the constructor, since it is used 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. 93 explicit BinHeap(ItemIntMap &map) : _iim(map) {} 94 95 /// \brief The constructor. 96 /// 97 /// The constructor. 98 /// \param map should be given to the constructor, since it is used 90 99 /// internally to handle the cross references. The value of the map 91 100 /// 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) {} 101 /// 102 /// \param comp The comparator function object. 103 BinHeap(ItemIntMap &map, const Compare &comp) 104 : _iim(map), _comp(comp) {} 104 105 105 106 … … 107 108 /// 108 109 /// \brief Returns the number of items stored in the heap. 109 int size() const { return data.size(); }110 int size() const { return _data.size(); } 110 111 111 112 /// \brief Checks if the heap stores no items. 112 113 /// 113 114 /// Returns \c true if and only if the heap stores no items. 114 bool empty() const { return data.empty(); }115 bool empty() const { return _data.empty(); } 115 116 116 117 /// \brief Make empty this heap. … … 121 122 /// each item to \c PRE_HEAP. 122 123 void clear() { 123 data.clear();124 _data.clear(); 124 125 } 125 126 … … 129 130 static int second_child(int i) { return 2*i+2; } 130 131 bool less(const Pair &p1, const Pair &p2) const { 131 return comp(p1.second, p2.second);132 return _comp(p1.second, p2.second); 132 133 } 133 134 134 135 int bubble_up(int hole, Pair p) { 135 136 int par = parent(hole); 136 while( hole>0 && less(p, data[par]) ) {137 move( data[par],hole);137 while( hole>0 && less(p,_data[par]) ) { 138 move(_data[par],hole); 138 139 hole = par; 139 140 par = parent(hole); … … 146 147 int child = second_child(hole); 147 148 while(child < length) { 148 if( less( data[child1],data[child]) ) {149 if( less(_data[child1], _data[child]) ) { 149 150 child; 150 151 } 151 if( !less( data[child], p) )152 if( !less(_data[child], p) ) 152 153 goto ok; 153 move( data[child], hole);154 move(_data[child], hole); 154 155 hole = child; 155 156 child = second_child(hole); 156 157 } 157 158 child; 158 if( child<length && less( data[child], p) ) {159 move( data[child], hole);159 if( child<length && less(_data[child], p) ) { 160 move(_data[child], hole); 160 161 hole=child; 161 162 } … … 166 167 167 168 void move(const Pair &p, int i) { 168 data[i] = p;169 iim.set(p.first, i);169 _data[i] = p; 170 _iim.set(p.first, i); 170 171 } 171 172 … … 176 177 /// \param p The pair to insert. 177 178 void push(const Pair &p) { 178 int n = data.size();179 data.resize(n+1);179 int n = _data.size(); 180 _data.resize(n+1); 180 181 bubble_up(n, p); 181 182 } … … 194 195 /// \pre The heap must be nonempty. 195 196 Item top() const { 196 return data[0].first;197 return _data[0].first; 197 198 } 198 199 … … 202 203 /// \pre The heap must be nonempty. 203 204 Prio prio() const { 204 return data[0].second;205 return _data[0].second; 205 206 } 206 207 … … 211 212 /// \pre The heap must be nonempty. 212 213 void pop() { 213 int n = data.size()1;214 iim.set(data[0].first, POST_HEAP);214 int n = _data.size()1; 215 _iim.set(_data[0].first, POST_HEAP); 215 216 if (n > 0) { 216 bubble_down(0, data[n], n);217 } 218 data.pop_back();217 bubble_down(0, _data[n], n); 218 } 219 _data.pop_back(); 219 220 } 220 221 … … 225 226 /// \pre The item should be in the heap. 226 227 void erase(const Item &i) { 227 int h = iim[i];228 int n = data.size()1;229 iim.set(data[h].first, POST_HEAP);228 int h = _iim[i]; 229 int n = _data.size()1; 230 _iim.set(_data[h].first, POST_HEAP); 230 231 if( h < n ) { 231 if ( bubble_up(h, data[n]) == h) {232 bubble_down(h, data[n], n);232 if ( bubble_up(h, _data[n]) == h) { 233 bubble_down(h, _data[n], n); 233 234 } 234 235 } 235 data.pop_back();236 _data.pop_back(); 236 237 } 237 238 … … 240 241 /// 241 242 /// This function returns the priority of item \c i. 243 /// \param i The item. 242 244 /// \pre \c i must be in the heap. 243 /// \param i The item.244 245 Prio operator[](const Item &i) const { 245 int idx = iim[i];246 return data[idx].second;246 int idx = _iim[i]; 247 return _data[idx].second; 247 248 } 248 249 … … 255 256 /// \param p The priority. 256 257 void set(const Item &i, const Prio &p) { 257 int idx = iim[i];258 int idx = _iim[i]; 258 259 if( idx < 0 ) { 259 260 push(i,p); 260 261 } 261 else if( comp(p,data[idx].second) ) {262 else if( _comp(p, _data[idx].second) ) { 262 263 bubble_up(idx, Pair(i,p)); 263 264 } 264 265 else { 265 bubble_down(idx, Pair(i,p), data.size());266 bubble_down(idx, Pair(i,p), _data.size()); 266 267 } 267 268 } … … 270 271 /// 271 272 /// This method decreases the priority of item \c i to \c p. 273 /// \param i The item. 274 /// \param p The priority. 272 275 /// \pre \c i must be stored in the heap with priority at least \c 273 276 /// p relative to \c Compare. 277 void decrease(const Item &i, const Prio &p) { 278 int idx = _iim[i]; 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. 274 285 /// \param i The item. 275 286 /// \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 287 /// \pre \c i must be stored in the heap with priority at most \c 285 288 /// p relative to \c Compare. 286 /// \param i The item.287 /// \param p The priority.288 289 void increase(const Item &i, const Prio &p) { 289 int idx = iim[i];290 bubble_down(idx, Pair(i,p), data.size());290 int idx = _iim[i]; 291 bubble_down(idx, Pair(i,p), _data.size()); 291 292 } 292 293 … … 300 301 /// \param i The item. 301 302 State state(const Item &i) const { 302 int s = iim[i];303 int s = _iim[i]; 303 304 if( s>=0 ) 304 305 s=0; … … 320 321 erase(i); 321 322 } 322 iim[i] = st;323 _iim[i] = st; 323 324 break; 324 325 case IN_HEAP: … … 334 335 /// with the same prioriority as prevoiusly the \c i item. 335 336 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;337 int idx = _iim[i]; 338 _iim.set(i, _iim[j]); 339 _iim.set(j, idx); 340 _data[idx].first = j; 340 341 } 341 342
Note: See TracChangeset
for help on using the changeset viewer.