1.1 --- a/lemon/binom_heap.h Mon Jul 20 19:06:39 2009 +0200
1.2 +++ b/lemon/binom_heap.h Fri Jul 24 01:07:45 2009 +0200
1.3 @@ -79,9 +79,9 @@
1.4 };
1.5
1.6 private:
1.7 - class store;
1.8 + class Store;
1.9
1.10 - std::vector<store> _data;
1.11 + std::vector<Store> _data;
1.12 int _min, _head;
1.13 ItemIntMap &_iim;
1.14 Compare _comp;
1.15 @@ -156,8 +156,9 @@
1.16 if ( i<0 ) {
1.17 int s=_data.size();
1.18 _iim.set( item,s );
1.19 - store st;
1.20 + Store st;
1.21 st.name=item;
1.22 + st.prio=value;
1.23 _data.push_back(st);
1.24 i=s;
1.25 }
1.26 @@ -165,14 +166,16 @@
1.27 _data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
1.28 _data[i].degree=0;
1.29 _data[i].in=true;
1.30 + _data[i].prio=value;
1.31 }
1.32 - _data[i].prio=value;
1.33
1.34 - if( 0==_num_items ) { _head=i; _min=i; }
1.35 - else { merge(i); }
1.36 -
1.37 - _min = findMin();
1.38 -
1.39 + if( 0==_num_items ) {
1.40 + _head=i;
1.41 + _min=i;
1.42 + } else {
1.43 + merge(i);
1.44 + if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
1.45 + }
1.46 ++_num_items;
1.47 }
1.48
1.49 @@ -208,26 +211,23 @@
1.50 if ( _data[_min].child!=-1 ) {
1.51 int child=_data[_min].child;
1.52 int neighb;
1.53 - int prev=-1;
1.54 while( child!=-1 ) {
1.55 neighb=_data[child].right_neighbor;
1.56 _data[child].parent=-1;
1.57 - _data[child].right_neighbor=prev;
1.58 + _data[child].right_neighbor=head_child;
1.59 head_child=child;
1.60 - prev=child;
1.61 child=neighb;
1.62 }
1.63 }
1.64
1.65 - // The first case is that there are only one root.
1.66 - if ( -1==_data[_head].right_neighbor ) {
1.67 + if ( _data[_head].right_neighbor==-1 ) {
1.68 + // there was only one root
1.69 _head=head_child;
1.70 }
1.71 - // The case where there are more roots.
1.72 else {
1.73 + // there were more roots
1.74 if( _head!=_min ) { unlace(_min); }
1.75 else { _head=_data[_head].right_neighbor; }
1.76 -
1.77 merge(head_child);
1.78 }
1.79 _min=findMin();
1.80 @@ -256,73 +256,20 @@
1.81 /// \pre \e item must be stored in the heap with priority at least \e value.
1.82 void decrease (Item item, const Prio& value) {
1.83 int i=_iim[item];
1.84 -
1.85 - if( _comp( value,_data[i].prio ) ) {
1.86 - _data[i].prio=value;
1.87 -
1.88 - int p_loc=_data[i].parent, loc=i;
1.89 - int parent, child, neighb;
1.90 -
1.91 - while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
1.92 -
1.93 - // parent set for other loc_child
1.94 - child=_data[loc].child;
1.95 - while( -1!=child ) {
1.96 - _data[child].parent=p_loc;
1.97 - child=_data[child].right_neighbor;
1.98 - }
1.99 -
1.100 - // parent set for other p_loc_child
1.101 - child=_data[p_loc].child;
1.102 - while( -1!=child ) {
1.103 - _data[child].parent=loc;
1.104 - child=_data[child].right_neighbor;
1.105 - }
1.106 -
1.107 - child=_data[p_loc].child;
1.108 - _data[p_loc].child=_data[loc].child;
1.109 - if( child==loc )
1.110 - child=p_loc;
1.111 - _data[loc].child=child;
1.112 -
1.113 - // left_neighb set for p_loc
1.114 - if( _data[loc].child!=p_loc ) {
1.115 - while( _data[child].right_neighbor!=loc )
1.116 - child=_data[child].right_neighbor;
1.117 - _data[child].right_neighbor=p_loc;
1.118 - }
1.119 -
1.120 - // left_neighb set for loc
1.121 - parent=_data[p_loc].parent;
1.122 - if( -1!=parent ) child=_data[parent].child;
1.123 - else child=_head;
1.124 -
1.125 - if( child!=p_loc ) {
1.126 - while( _data[child].right_neighbor!=p_loc )
1.127 - child=_data[child].right_neighbor;
1.128 - _data[child].right_neighbor=loc;
1.129 - }
1.130 -
1.131 - neighb=_data[p_loc].right_neighbor;
1.132 - _data[p_loc].right_neighbor=_data[loc].right_neighbor;
1.133 - _data[loc].right_neighbor=neighb;
1.134 -
1.135 - _data[p_loc].parent=loc;
1.136 - _data[loc].parent=parent;
1.137 -
1.138 - if( -1!=parent && _data[parent].child==p_loc )
1.139 - _data[parent].child=loc;
1.140 -
1.141 - /*if new parent will be the first root*/
1.142 - if( _head==p_loc )
1.143 - _head=loc;
1.144 -
1.145 - p_loc=_data[loc].parent;
1.146 - }
1.147 + int p=_data[i].parent;
1.148 + _data[i].prio=value;
1.149 +
1.150 + while( p!=-1 && _comp(value, _data[p].prio) ) {
1.151 + _data[i].name=_data[p].name;
1.152 + _data[i].prio=_data[p].prio;
1.153 + _data[p].name=item;
1.154 + _data[p].prio=value;
1.155 + _iim[_data[i].name]=i;
1.156 + i=p;
1.157 + p=_data[p].parent;
1.158 }
1.159 - if( _comp(value,_data[_min].prio) ) {
1.160 - _min=i;
1.161 - }
1.162 + _iim[item]=i;
1.163 + if ( _comp(value, _data[_min].prio) ) _min=i;
1.164 }
1.165
1.166 /// \brief Increase the priority of an item to the given value.
1.167 @@ -375,104 +322,87 @@
1.168 }
1.169
1.170 private:
1.171 +
1.172 + // Find the minimum of the roots
1.173 int findMin() {
1.174 - int min_loc=-1, min_val;
1.175 - int x=_head;
1.176 - if( x!=-1 ) {
1.177 - min_val=_data[x].prio;
1.178 - min_loc=x;
1.179 - x=_data[x].right_neighbor;
1.180 -
1.181 - while( x!=-1 ) {
1.182 + if( _head!=-1 ) {
1.183 + int min_loc=_head, min_val=_data[_head].prio;
1.184 + for( int x=_data[_head].right_neighbor; x!=-1;
1.185 + x=_data[x].right_neighbor ) {
1.186 if( _comp( _data[x].prio,min_val ) ) {
1.187 min_val=_data[x].prio;
1.188 min_loc=x;
1.189 }
1.190 - x=_data[x].right_neighbor;
1.191 }
1.192 + return min_loc;
1.193 }
1.194 - return min_loc;
1.195 + else return -1;
1.196 }
1.197
1.198 + // Merge the heap with another heap starting at the given position
1.199 void merge(int a) {
1.200 - interleave(a);
1.201 -
1.202 + if( _head==-1 || a==-1 ) return;
1.203 + if( _data[a].right_neighbor==-1 &&
1.204 + _data[a].degree<=_data[_head].degree ) {
1.205 + _data[a].right_neighbor=_head;
1.206 + _head=a;
1.207 + } else {
1.208 + interleave(a);
1.209 + }
1.210 + if( _data[_head].right_neighbor==-1 ) return;
1.211 +
1.212 int x=_head;
1.213 - if( -1!=x ) {
1.214 - int x_prev=-1, x_next=_data[x].right_neighbor;
1.215 - while( -1!=x_next ) {
1.216 - if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
1.217 - x_prev=x;
1.218 + int x_prev=-1, x_next=_data[x].right_neighbor;
1.219 + while( x_next!=-1 ) {
1.220 + if( _data[x].degree!=_data[x_next].degree ||
1.221 + ( _data[x_next].right_neighbor!=-1 &&
1.222 + _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
1.223 + x_prev=x;
1.224 + x=x_next;
1.225 + }
1.226 + else {
1.227 + if( _comp(_data[x_next].prio,_data[x].prio) ) {
1.228 + if( x_prev==-1 ) {
1.229 + _head=x_next;
1.230 + } else {
1.231 + _data[x_prev].right_neighbor=x_next;
1.232 + }
1.233 + fuse(x,x_next);
1.234 x=x_next;
1.235 }
1.236 else {
1.237 - if( _comp(_data[x].prio,_data[x_next].prio) ) {
1.238 - _data[x].right_neighbor=_data[x_next].right_neighbor;
1.239 - fuse(x_next,x);
1.240 - }
1.241 - else {
1.242 - if( -1==x_prev ) { _head=x_next; }
1.243 - else {
1.244 - _data[x_prev].right_neighbor=x_next;
1.245 - }
1.246 - fuse(x,x_next);
1.247 - x=x_next;
1.248 - }
1.249 + _data[x].right_neighbor=_data[x_next].right_neighbor;
1.250 + fuse(x_next,x);
1.251 }
1.252 - x_next=_data[x].right_neighbor;
1.253 }
1.254 + x_next=_data[x].right_neighbor;
1.255 }
1.256 }
1.257
1.258 + // Interleave the elements of the given list into the list of the roots
1.259 void interleave(int a) {
1.260 - int other=-1, head_other=-1;
1.261 -
1.262 - while( -1!=a || -1!=_head ) {
1.263 - if( -1==a ) {
1.264 - if( -1==head_other ) {
1.265 - head_other=_head;
1.266 - }
1.267 - else {
1.268 - _data[other].right_neighbor=_head;
1.269 - }
1.270 - _head=-1;
1.271 - }
1.272 - else if( -1==_head ) {
1.273 - if( -1==head_other ) {
1.274 - head_other=a;
1.275 - }
1.276 - else {
1.277 - _data[other].right_neighbor=a;
1.278 - }
1.279 - a=-1;
1.280 + int p=_head, q=a;
1.281 + int curr=_data.size();
1.282 + _data.push_back(Store());
1.283 +
1.284 + while( p!=-1 || q!=-1 ) {
1.285 + if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
1.286 + _data[curr].right_neighbor=p;
1.287 + curr=p;
1.288 + p=_data[p].right_neighbor;
1.289 }
1.290 else {
1.291 - if( _data[a].degree<_data[_head].degree ) {
1.292 - if( -1==head_other ) {
1.293 - head_other=a;
1.294 - }
1.295 - else {
1.296 - _data[other].right_neighbor=a;
1.297 - }
1.298 - other=a;
1.299 - a=_data[a].right_neighbor;
1.300 - }
1.301 - else {
1.302 - if( -1==head_other ) {
1.303 - head_other=_head;
1.304 - }
1.305 - else {
1.306 - _data[other].right_neighbor=_head;
1.307 - }
1.308 - other=_head;
1.309 - _head=_data[_head].right_neighbor;
1.310 - }
1.311 + _data[curr].right_neighbor=q;
1.312 + curr=q;
1.313 + q=_data[q].right_neighbor;
1.314 }
1.315 }
1.316 - _head=head_other;
1.317 +
1.318 + _head=_data.back().right_neighbor;
1.319 + _data.pop_back();
1.320 }
1.321
1.322 - // Lacing a under b
1.323 + // Lace node a under node b
1.324 void fuse(int a, int b) {
1.325 _data[a].parent=b;
1.326 _data[a].right_neighbor=_data[b].child;
1.327 @@ -481,7 +411,7 @@
1.328 ++_data[b].degree;
1.329 }
1.330
1.331 - // It is invoked only if a has siblings.
1.332 + // Unlace node a (if it has siblings)
1.333 void unlace(int a) {
1.334 int neighb=_data[a].right_neighbor;
1.335 int other=_head;
1.336 @@ -493,7 +423,7 @@
1.337
1.338 private:
1.339
1.340 - class store {
1.341 + class Store {
1.342 friend class BinomHeap;
1.343
1.344 Item name;
1.345 @@ -504,7 +434,8 @@
1.346 bool in;
1.347 Prio prio;
1.348
1.349 - store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
1.350 + Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
1.351 + in(true) {}
1.352 };
1.353 };
1.354