Changeset 2546:b5eba564bb60 in lemon-0.x
- Timestamp:
- 12/20/07 16:21:22 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3423
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bin_heap.h
r2529 r2546 121 121 private: 122 122 static int parent(int i) { return (i-1)/2; } 123 123 124 static int second_child(int i) { return 2*i+2; } 124 125 bool less(const PairType &p1, const PairType &p2) const { … … 126 127 } 127 128 128 int bubble_up(int hole, PairType p); 129 int bubble_down(int hole, PairType p, int length); 129 int bubble_up(int hole, PairType p) { 130 int par = parent(hole); 131 while( hole>0 && less(p,data[par]) ) { 132 move(data[par],hole); 133 hole = par; 134 par = parent(hole); 135 } 136 move(p, hole); 137 return hole; 138 } 139 140 int bubble_down(int hole, PairType p, int length) { 141 int child = second_child(hole); 142 while(child < length) { 143 if( less(data[child-1], data[child]) ) { 144 --child; 145 } 146 if( !less(data[child], p) ) 147 goto ok; 148 move(data[child], hole); 149 hole = child; 150 child = second_child(hole); 151 } 152 child--; 153 if( child<length && less(data[child], p) ) { 154 move(data[child], hole); 155 hole=child; 156 } 157 ok: 158 move(p, hole); 159 return hole; 160 } 130 161 131 162 void move(const PairType &p, int i) { 132 163 data[i] = p; 133 164 iim.set(p.first, i); 134 }135 136 void rmidx(int h) {137 int n = data.size()-1;138 if( h>=0 && h<=n ) {139 iim.set(data[h].first, POST_HEAP);140 if ( h<n ) {141 bubble_down(h, data[n], n);142 }143 data.pop_back();144 }145 165 } 146 166 … … 186 206 /// \pre The heap must be non-empty. 187 207 void pop() { 188 rmidx(0); 208 int n = data.size()-1; 209 iim.set(data[0].first, POST_HEAP); 210 if (n > 0) { 211 bubble_down(0, data[n], n); 212 } 213 data.pop_back(); 189 214 } 190 215 191 216 /// \brief Deletes \c i from the heap. 192 217 /// 193 /// This method deletes item \c i from the heap , if \c i was194 /// already stored in the heap.195 /// \p aram i The item to erase.218 /// This method deletes item \c i from the heap. 219 /// \param i The item to erase. 220 /// \pre The item should be in the heap. 196 221 void erase(const ItemType &i) { 197 rmidx(iim[i]); 222 int h = iim[i]; 223 int n = data.size()-1; 224 iim.set(data[h].first, POST_HEAP); 225 if( h < n ) { 226 if ( bubble_up(h, data[n]) == h) { 227 bubble_down(h, data[n], n); 228 } 229 } 230 data.pop_back(); 198 231 } 199 232 … … 290 323 291 324 }; // class BinHeap 292 293 325 294 template <typename V, typename M, typename C>295 int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {296 int par = parent(hole);297 while( hole>0 && less(p,data[par]) ) {298 move(data[par],hole);299 hole = par;300 par = parent(hole);301 }302 move(p, hole);303 return hole;304 }305 306 template <typename V, typename M, typename C>307 int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {308 int child = second_child(hole);309 while(child < length) {310 if( less(data[child-1], data[child]) ) {311 --child;312 }313 if( !less(data[child], p) )314 goto ok;315 move(data[child], hole);316 hole = child;317 child = second_child(hole);318 }319 child--;320 if( child<length && less(data[child], p) ) {321 move(data[child], hole);322 hole=child;323 }324 ok:325 move(p, hole);326 return hole;327 }328 329 330 326 } // namespace lemon 331 327
Note: See TracChangeset
for help on using the changeset viewer.