Changeset 209:765619b7cbb2 in lemon for lemon/bin_heap.h
 Timestamp:
 07/13/08 20:51:02 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bin_heap.h
r157 r209 1 /* * C++*2 * 3 * This file is a part of LEMON, a generic C++ optimization library 1 /* * mode: C++; indenttabsmode: nil; * 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 20032008 … … 49 49 ///\sa Dijkstra 50 50 template <typename _Prio, typename _ItemIntMap, 51 51 typename _Compare = std::less<_Prio> > 52 52 class BinHeap { 53 53 … … 91 91 /// should be PRE_HEAP (1) for each element. 92 92 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 93 93 94 94 /// \brief The constructor. 95 95 /// … … 100 100 /// 101 101 /// \param _comp The comparator function object. 102 BinHeap(ItemIntMap &_iim, const Compare &_comp) 102 BinHeap(ItemIntMap &_iim, const Compare &_comp) 103 103 : iim(_iim), comp(_comp) {} 104 104 … … 108 108 /// \brief Returns the number of items stored in the heap. 109 109 int size() const { return data.size(); } 110 110 111 111 /// \brief Checks if the heap stores no items. 112 112 /// … … 115 115 116 116 /// \brief Make empty this heap. 117 /// 117 /// 118 118 /// Make empty this heap. It does not change the cross reference map. 119 119 /// If you want to reuse what is not surely empty you should first clear 120 120 /// the heap and after that you should set the cross reference map for 121 121 /// each item to \c PRE_HEAP. 122 void clear() { 123 data.clear(); 122 void clear() { 123 data.clear(); 124 124 } 125 125 … … 135 135 int par = parent(hole); 136 136 while( hole>0 && less(p,data[par]) ) { 137 138 139 137 move(data[par],hole); 138 hole = par; 139 par = parent(hole); 140 140 } 141 141 move(p, hole); … … 146 146 int child = second_child(hole); 147 147 while(child < length) { 148 149 150 151 152 153 154 155 148 if( less(data[child1], 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 156 } 157 157 child; 158 158 if( child<length && less(data[child], p) ) { 159 160 159 move(data[child], hole); 160 hole=child; 161 161 } 162 162 ok: … … 182 182 183 183 /// \brief Insert an item into the heap with the given heap. 184 /// 185 /// Adds \c i to the heap with priority \c p. 184 /// 185 /// Adds \c i to the heap with priority \c p. 186 186 /// \param i The item to insert. 187 187 /// \param p The priority of the item. … … 191 191 /// 192 192 /// This method returns the item with minimum priority relative to \c 193 /// Compare. 194 /// \pre The heap must be nonempty. 193 /// Compare. 194 /// \pre The heap must be nonempty. 195 195 Item top() const { 196 196 return data[0].first; … … 208 208 /// 209 209 /// This method deletes the item with minimum priority relative to \c 210 /// Compare from the heap. 211 /// \pre The heap must be nonempty. 210 /// Compare from the heap. 211 /// \pre The heap must be nonempty. 212 212 void pop() { 213 213 int n = data.size()1; 214 214 iim.set(data[0].first, POST_HEAP); 215 215 if (n > 0) { 216 216 bubble_down(0, data[n], n); 217 217 } 218 218 data.pop_back(); … … 229 229 iim.set(data[h].first, POST_HEAP); 230 230 if( h < n ) { 231 232 233 231 if ( bubble_up(h, data[n]) == h) { 232 bubble_down(h, data[n], n); 233 } 234 234 } 235 235 data.pop_back(); 236 236 } 237 237 238 238 239 239 /// \brief Returns the priority of \c i. 240 240 /// 241 /// This function returns the priority of item \c i. 241 /// This function returns the priority of item \c i. 242 242 /// \pre \c i must be in the heap. 243 243 /// \param i The item. … … 247 247 } 248 248 249 /// \brief \c i gets to the heap with priority \c p independently 249 /// \brief \c i gets to the heap with priority \c p independently 250 250 /// if \c i was already there. 251 251 /// … … 257 257 int idx = iim[i]; 258 258 if( idx < 0 ) { 259 259 push(i,p); 260 260 } 261 261 else if( comp(p, data[idx].second) ) { 262 262 bubble_up(idx, Pair(i,p)); 263 263 } 264 264 else { 265 265 bubble_down(idx, Pair(i,p), data.size()); 266 266 } 267 267 } … … 278 278 bubble_up(idx, Pair(i,p)); 279 279 } 280 280 281 281 /// \brief Increases the priority of \c i to \c p. 282 282 /// 283 /// This method sets the priority of item \c i to \c p. 283 /// This method sets the priority of item \c i to \c p. 284 284 /// \pre \c i must be stored in the heap with priority at most \c 285 285 /// p relative to \c Compare. … … 291 291 } 292 292 293 /// \brief Returns if \c item is in, has already been in, or has 293 /// \brief Returns if \c item is in, has already been in, or has 294 294 /// never been in the heap. 295 295 /// … … 302 302 int s = iim[i]; 303 303 if( s>=0 ) 304 304 s=0; 305 305 return State(s); 306 306 } … … 312 312 /// better time complexity. 313 313 /// \param i The item. 314 /// \param st The state. It should not be \c IN_HEAP. 314 /// \param st The state. It should not be \c IN_HEAP. 315 315 void state(const Item& i, State st) { 316 316 switch (st) { … … 341 341 342 342 }; // class BinHeap 343 343 344 344 } // namespace lemon 345 345
Note: See TracChangeset
for help on using the changeset viewer.