lemon/fib_heap.h
changeset 842 c2ff0a365245
parent 710 f1fe0ddad6f7
equal deleted inserted replaced
3:bbb0aee237b1 4:87def784ec4c
   186     void pop() {
   186     void pop() {
   187       /*The first case is that there are only one root.*/
   187       /*The first case is that there are only one root.*/
   188       if ( _data[_minimum].left_neighbor==_minimum ) {
   188       if ( _data[_minimum].left_neighbor==_minimum ) {
   189         _data[_minimum].in=false;
   189         _data[_minimum].in=false;
   190         if ( _data[_minimum].degree!=0 ) {
   190         if ( _data[_minimum].degree!=0 ) {
   191           makeroot(_data[_minimum].child);
   191           makeRoot(_data[_minimum].child);
   192           _minimum=_data[_minimum].child;
   192           _minimum=_data[_minimum].child;
   193           balance();
   193           balance();
   194         }
   194         }
   195       } else {
   195       } else {
   196         int right=_data[_minimum].right_neighbor;
   196         int right=_data[_minimum].right_neighbor;
   199         if ( _data[_minimum].degree > 0 ) {
   199         if ( _data[_minimum].degree > 0 ) {
   200           int left=_data[_minimum].left_neighbor;
   200           int left=_data[_minimum].left_neighbor;
   201           int child=_data[_minimum].child;
   201           int child=_data[_minimum].child;
   202           int last_child=_data[child].left_neighbor;
   202           int last_child=_data[child].left_neighbor;
   203 
   203 
   204           makeroot(child);
   204           makeRoot(child);
   205 
   205 
   206           _data[left].right_neighbor=child;
   206           _data[left].right_neighbor=child;
   207           _data[child].left_neighbor=left;
   207           _data[child].left_neighbor=left;
   208           _data[right].left_neighbor=last_child;
   208           _data[right].left_neighbor=last_child;
   209           _data[last_child].right_neighbor=right;
   209           _data[last_child].right_neighbor=right;
   370         if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
   370         if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s;
   371         s=_data[s].right_neighbor;
   371         s=_data[s].right_neighbor;
   372       } while ( s != m );
   372       } while ( s != m );
   373     }
   373     }
   374 
   374 
   375     void makeroot(int c) {
   375     void makeRoot(int c) {
   376       int s=c;
   376       int s=c;
   377       do {
   377       do {
   378         _data[s].parent=-1;
   378         _data[s].parent=-1;
   379         s=_data[s].right_neighbor;
   379         s=_data[s].right_neighbor;
   380       } while ( s != c );
   380       } while ( s != c );