# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1248390465 -7200
# Node ID 3887d6f994d7468f03e51eb8d7ead0683421793a
# Parent 9314d9339475d4747dceb17b8f34d0bbc77d6b93
Much faster implementation for BinomHeap (#301)
diff -r 9314d9339475 -r 3887d6f994d7 lemon/binom_heap.h
--- a/lemon/binom_heap.h Mon Jul 20 19:06:39 2009 +0200
+++ b/lemon/binom_heap.h Fri Jul 24 01:07:45 2009 +0200
@@ -79,9 +79,9 @@
};
private:
- class store;
+ class Store;
- std::vector<store> _data;
+ std::vector<Store> _data;
int _min, _head;
ItemIntMap &_iim;
Compare _comp;
@@ -156,8 +156,9 @@
if ( i<0 ) {
int s=_data.size();
_iim.set( item,s );
- store st;
+ Store st;
st.name=item;
+ st.prio=value;
_data.push_back(st);
i=s;
}
@@ -165,14 +166,16 @@
_data[i].parent=_data[i].right_neighbor=_data[i].child=-1;
_data[i].degree=0;
_data[i].in=true;
+ _data[i].prio=value;
}
- _data[i].prio=value;
- if( 0==_num_items ) { _head=i; _min=i; }
- else { merge(i); }
-
- _min = findMin();
-
+ if( 0==_num_items ) {
+ _head=i;
+ _min=i;
+ } else {
+ merge(i);
+ if( _comp(_data[i].prio, _data[_min].prio) ) _min=i;
+ }
++_num_items;
}
@@ -208,26 +211,23 @@
if ( _data[_min].child!=-1 ) {
int child=_data[_min].child;
int neighb;
- int prev=-1;
while( child!=-1 ) {
neighb=_data[child].right_neighbor;
_data[child].parent=-1;
- _data[child].right_neighbor=prev;
+ _data[child].right_neighbor=head_child;
head_child=child;
- prev=child;
child=neighb;
}
}
- // The first case is that there are only one root.
- if ( -1==_data[_head].right_neighbor ) {
+ if ( _data[_head].right_neighbor==-1 ) {
+ // there was only one root
_head=head_child;
}
- // The case where there are more roots.
else {
+ // there were more roots
if( _head!=_min ) { unlace(_min); }
else { _head=_data[_head].right_neighbor; }
-
merge(head_child);
}
_min=findMin();
@@ -256,73 +256,20 @@
/// \pre \e item must be stored in the heap with priority at least \e value.
void decrease (Item item, const Prio& value) {
int i=_iim[item];
-
- if( _comp( value,_data[i].prio ) ) {
- _data[i].prio=value;
-
- int p_loc=_data[i].parent, loc=i;
- int parent, child, neighb;
-
- while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) {
-
- // parent set for other loc_child
- child=_data[loc].child;
- while( -1!=child ) {
- _data[child].parent=p_loc;
- child=_data[child].right_neighbor;
- }
-
- // parent set for other p_loc_child
- child=_data[p_loc].child;
- while( -1!=child ) {
- _data[child].parent=loc;
- child=_data[child].right_neighbor;
- }
-
- child=_data[p_loc].child;
- _data[p_loc].child=_data[loc].child;
- if( child==loc )
- child=p_loc;
- _data[loc].child=child;
-
- // left_neighb set for p_loc
- if( _data[loc].child!=p_loc ) {
- while( _data[child].right_neighbor!=loc )
- child=_data[child].right_neighbor;
- _data[child].right_neighbor=p_loc;
- }
-
- // left_neighb set for loc
- parent=_data[p_loc].parent;
- if( -1!=parent ) child=_data[parent].child;
- else child=_head;
-
- if( child!=p_loc ) {
- while( _data[child].right_neighbor!=p_loc )
- child=_data[child].right_neighbor;
- _data[child].right_neighbor=loc;
- }
-
- neighb=_data[p_loc].right_neighbor;
- _data[p_loc].right_neighbor=_data[loc].right_neighbor;
- _data[loc].right_neighbor=neighb;
-
- _data[p_loc].parent=loc;
- _data[loc].parent=parent;
-
- if( -1!=parent && _data[parent].child==p_loc )
- _data[parent].child=loc;
-
- /*if new parent will be the first root*/
- if( _head==p_loc )
- _head=loc;
-
- p_loc=_data[loc].parent;
- }
+ int p=_data[i].parent;
+ _data[i].prio=value;
+
+ while( p!=-1 && _comp(value, _data[p].prio) ) {
+ _data[i].name=_data[p].name;
+ _data[i].prio=_data[p].prio;
+ _data[p].name=item;
+ _data[p].prio=value;
+ _iim[_data[i].name]=i;
+ i=p;
+ p=_data[p].parent;
}
- if( _comp(value,_data[_min].prio) ) {
- _min=i;
- }
+ _iim[item]=i;
+ if ( _comp(value, _data[_min].prio) ) _min=i;
}
/// \brief Increase the priority of an item to the given value.
@@ -375,104 +322,87 @@
}
private:
+
+ // Find the minimum of the roots
int findMin() {
- int min_loc=-1, min_val;
- int x=_head;
- if( x!=-1 ) {
- min_val=_data[x].prio;
- min_loc=x;
- x=_data[x].right_neighbor;
-
- while( x!=-1 ) {
+ if( _head!=-1 ) {
+ int min_loc=_head, min_val=_data[_head].prio;
+ for( int x=_data[_head].right_neighbor; x!=-1;
+ x=_data[x].right_neighbor ) {
if( _comp( _data[x].prio,min_val ) ) {
min_val=_data[x].prio;
min_loc=x;
}
- x=_data[x].right_neighbor;
}
+ return min_loc;
}
- return min_loc;
+ else return -1;
}
+ // Merge the heap with another heap starting at the given position
void merge(int a) {
- interleave(a);
-
+ if( _head==-1 || a==-1 ) return;
+ if( _data[a].right_neighbor==-1 &&
+ _data[a].degree<=_data[_head].degree ) {
+ _data[a].right_neighbor=_head;
+ _head=a;
+ } else {
+ interleave(a);
+ }
+ if( _data[_head].right_neighbor==-1 ) return;
+
int x=_head;
- if( -1!=x ) {
- int x_prev=-1, x_next=_data[x].right_neighbor;
- while( -1!=x_next ) {
- if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
- x_prev=x;
+ int x_prev=-1, x_next=_data[x].right_neighbor;
+ while( x_next!=-1 ) {
+ if( _data[x].degree!=_data[x_next].degree ||
+ ( _data[x_next].right_neighbor!=-1 &&
+ _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) {
+ x_prev=x;
+ x=x_next;
+ }
+ else {
+ if( _comp(_data[x_next].prio,_data[x].prio) ) {
+ if( x_prev==-1 ) {
+ _head=x_next;
+ } else {
+ _data[x_prev].right_neighbor=x_next;
+ }
+ fuse(x,x_next);
x=x_next;
}
else {
- if( _comp(_data[x].prio,_data[x_next].prio) ) {
- _data[x].right_neighbor=_data[x_next].right_neighbor;
- fuse(x_next,x);
- }
- else {
- if( -1==x_prev ) { _head=x_next; }
- else {
- _data[x_prev].right_neighbor=x_next;
- }
- fuse(x,x_next);
- x=x_next;
- }
+ _data[x].right_neighbor=_data[x_next].right_neighbor;
+ fuse(x_next,x);
}
- x_next=_data[x].right_neighbor;
}
+ x_next=_data[x].right_neighbor;
}
}
+ // Interleave the elements of the given list into the list of the roots
void interleave(int a) {
- int other=-1, head_other=-1;
-
- while( -1!=a || -1!=_head ) {
- if( -1==a ) {
- if( -1==head_other ) {
- head_other=_head;
- }
- else {
- _data[other].right_neighbor=_head;
- }
- _head=-1;
- }
- else if( -1==_head ) {
- if( -1==head_other ) {
- head_other=a;
- }
- else {
- _data[other].right_neighbor=a;
- }
- a=-1;
+ int p=_head, q=a;
+ int curr=_data.size();
+ _data.push_back(Store());
+
+ while( p!=-1 || q!=-1 ) {
+ if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) {
+ _data[curr].right_neighbor=p;
+ curr=p;
+ p=_data[p].right_neighbor;
}
else {
- if( _data[a].degree<_data[_head].degree ) {
- if( -1==head_other ) {
- head_other=a;
- }
- else {
- _data[other].right_neighbor=a;
- }
- other=a;
- a=_data[a].right_neighbor;
- }
- else {
- if( -1==head_other ) {
- head_other=_head;
- }
- else {
- _data[other].right_neighbor=_head;
- }
- other=_head;
- _head=_data[_head].right_neighbor;
- }
+ _data[curr].right_neighbor=q;
+ curr=q;
+ q=_data[q].right_neighbor;
}
}
- _head=head_other;
+
+ _head=_data.back().right_neighbor;
+ _data.pop_back();
}
- // Lacing a under b
+ // Lace node a under node b
void fuse(int a, int b) {
_data[a].parent=b;
_data[a].right_neighbor=_data[b].child;
@@ -481,7 +411,7 @@
++_data[b].degree;
}
- // It is invoked only if a has siblings.
+ // Unlace node a (if it has siblings)
void unlace(int a) {
int neighb=_data[a].right_neighbor;
int other=_head;
@@ -493,7 +423,7 @@
private:
- class store {
+ class Store {
friend class BinomHeap;
Item name;
@@ -504,7 +434,8 @@
bool in;
Prio prio;
- store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {}
+ Store() : parent(-1), right_neighbor(-1), child(-1), degree(0),
+ in(true) {}
};
};