lemon/fourary_heap.h
changeset 732 1f8ad32f088b
parent 705 39a5b48bcace
equal deleted inserted replaced
2:da888a4a0d39 3:39126be526c6
   129 
   129 
   130     bool less(const Pair &p1, const Pair &p2) const {
   130     bool less(const Pair &p1, const Pair &p2) const {
   131       return _comp(p1.second, p2.second);
   131       return _comp(p1.second, p2.second);
   132     }
   132     }
   133 
   133 
   134     int findMin(const int child, const int length) {
       
   135       int min=child;
       
   136       if( child+3<length ) {
       
   137         if( less(_data[child+3], _data[min]) )
       
   138           min=child+3;
       
   139         if( less(_data[child+2], _data[min]) )
       
   140           min=child+2;
       
   141         if( less(_data[child+1], _data[min]) )
       
   142           min=child+1;
       
   143       }
       
   144       else if( child+2<length ) {
       
   145         if( less(_data[child+2], _data[min]) )
       
   146           min=child+2;
       
   147         if( less(_data[child+1], _data[min]) )
       
   148           min=child+1;
       
   149       }
       
   150       else if( child+1<length ) {
       
   151         if( less(_data[child+1], _data[min]) )
       
   152           min=child+1;
       
   153       }
       
   154       return min;
       
   155     }
       
   156 
       
   157     void bubbleUp(int hole, Pair p) {
   134     void bubbleUp(int hole, Pair p) {
   158       int par = parent(hole);
   135       int par = parent(hole);
   159       while( hole>0 && less(p,_data[par]) ) {
   136       while( hole>0 && less(p,_data[par]) ) {
   160         move(_data[par],hole);
   137         move(_data[par],hole);
   161         hole = par;
   138         hole = par;
   165     }
   142     }
   166 
   143 
   167     void bubbleDown(int hole, Pair p, int length) {
   144     void bubbleDown(int hole, Pair p, int length) {
   168       if( length>1 ) {
   145       if( length>1 ) {
   169         int child = firstChild(hole);
   146         int child = firstChild(hole);
   170         while( child<length ) {
   147         while( child+3<length ) {
   171           child = findMin(child, length);
   148           int min=child;
   172           if( !less(_data[child], p) )
   149           if( less(_data[++child], _data[min]) ) min=child;
       
   150           if( less(_data[++child], _data[min]) ) min=child;
       
   151           if( less(_data[++child], _data[min]) ) min=child;
       
   152           if( !less(_data[min], p) )
   173             goto ok;
   153             goto ok;
   174           move(_data[child], hole);
   154           move(_data[min], hole);
   175           hole = child;
   155           hole = min;
   176           child = firstChild(hole);
   156           child = firstChild(hole);
       
   157         }
       
   158         if ( child<length ) {
       
   159           int min = child;
       
   160           if( ++child<length && less(_data[child], _data[min]) ) min=child;
       
   161           if( ++child<length && less(_data[child], _data[min]) ) min=child;
       
   162           if( less(_data[min], p) ) {
       
   163             move(_data[min], hole);
       
   164             hole = min;
       
   165           }
   177         }
   166         }
   178       }
   167       }
   179     ok:
   168     ok:
   180       move(p, hole);
   169       move(p, hole);
   181     }
   170     }