lemon/kary_heap.h
changeset 815 aef153f430e1
parent 704 7124b2581f72
equal deleted inserted replaced
2:44a3f78187f4 3:1904302e42ef
   136 
   136 
   137     bool less(const Pair &p1, const Pair &p2) const {
   137     bool less(const Pair &p1, const Pair &p2) const {
   138       return _comp(p1.second, p2.second);
   138       return _comp(p1.second, p2.second);
   139     }
   139     }
   140 
   140 
   141     int findMin(const int child, const int length) {
       
   142       int min=child, i=1;
       
   143       while( i<K && child+i<length ) {
       
   144         if( less(_data[child+i], _data[min]) )
       
   145           min=child+i;
       
   146         ++i;
       
   147       }
       
   148       return min;
       
   149     }
       
   150 
       
   151     void bubbleUp(int hole, Pair p) {
   141     void bubbleUp(int hole, Pair p) {
   152       int par = parent(hole);
   142       int par = parent(hole);
   153       while( hole>0 && less(p,_data[par]) ) {
   143       while( hole>0 && less(p,_data[par]) ) {
   154         move(_data[par],hole);
   144         move(_data[par],hole);
   155         hole = par;
   145         hole = par;
   159     }
   149     }
   160 
   150 
   161     void bubbleDown(int hole, Pair p, int length) {
   151     void bubbleDown(int hole, Pair p, int length) {
   162       if( length>1 ) {
   152       if( length>1 ) {
   163         int child = firstChild(hole);
   153         int child = firstChild(hole);
   164         while( child<length ) {
   154         while( child+K<=length ) {
   165           child = findMin(child, length);
   155           int min=child;
   166           if( !less(_data[child], p) )
   156           for (int i=1; i<K; ++i) {
       
   157             if( less(_data[child+i], _data[min]) )
       
   158               min=child+i;
       
   159           }
       
   160           if( !less(_data[min], p) )
   167             goto ok;
   161             goto ok;
   168           move(_data[child], hole);
   162           move(_data[min], hole);
   169           hole = child;
   163           hole = min;
   170           child = firstChild(hole);
   164           child = firstChild(hole);
       
   165         }
       
   166         if ( child<length ) {
       
   167           int min = child;
       
   168           while (++child < length) {
       
   169             if( less(_data[child], _data[min]) )
       
   170               min=child;
       
   171           }
       
   172           if( less(_data[min], p) ) {
       
   173             move(_data[min], hole);
       
   174             hole = min;
       
   175           }
   171         }
   176         }
   172       }
   177       }
   173     ok:
   178     ok:
   174       move(p, hole);
   179       move(p, hole);
   175     }
   180     }