lemon/bin_heap.h
changeset 711 28cfac049a6a
parent 710 f1fe0ddad6f7
child 1092 dceba191c00d
     1.1 --- a/lemon/bin_heap.h	Wed Jul 08 17:22:36 2009 +0200
     1.2 +++ b/lemon/bin_heap.h	Wed Jul 08 17:47:01 2009 +0200
     1.3 @@ -124,12 +124,12 @@
     1.4    private:
     1.5      static int parent(int i) { return (i-1)/2; }
     1.6  
     1.7 -    static int second_child(int i) { return 2*i+2; }
     1.8 +    static int secondChild(int i) { return 2*i+2; }
     1.9      bool less(const Pair &p1, const Pair &p2) const {
    1.10        return _comp(p1.second, p2.second);
    1.11      }
    1.12  
    1.13 -    int bubble_up(int hole, Pair p) {
    1.14 +    int bubbleUp(int hole, Pair p) {
    1.15        int par = parent(hole);
    1.16        while( hole>0 && less(p,_data[par]) ) {
    1.17          move(_data[par],hole);
    1.18 @@ -140,8 +140,8 @@
    1.19        return hole;
    1.20      }
    1.21  
    1.22 -    int bubble_down(int hole, Pair p, int length) {
    1.23 -      int child = second_child(hole);
    1.24 +    int bubbleDown(int hole, Pair p, int length) {
    1.25 +      int child = secondChild(hole);
    1.26        while(child < length) {
    1.27          if( less(_data[child-1], _data[child]) ) {
    1.28            --child;
    1.29 @@ -150,7 +150,7 @@
    1.30            goto ok;
    1.31          move(_data[child], hole);
    1.32          hole = child;
    1.33 -        child = second_child(hole);
    1.34 +        child = secondChild(hole);
    1.35        }
    1.36        child--;
    1.37        if( child<length && less(_data[child], p) ) {
    1.38 @@ -178,7 +178,7 @@
    1.39      void push(const Pair &p) {
    1.40        int n = _data.size();
    1.41        _data.resize(n+1);
    1.42 -      bubble_up(n, p);
    1.43 +      bubbleUp(n, p);
    1.44      }
    1.45  
    1.46      /// \brief Insert an item into the heap with the given priority.
    1.47 @@ -214,7 +214,7 @@
    1.48        int n = _data.size()-1;
    1.49        _iim.set(_data[0].first, POST_HEAP);
    1.50        if (n > 0) {
    1.51 -        bubble_down(0, _data[n], n);
    1.52 +        bubbleDown(0, _data[n], n);
    1.53        }
    1.54        _data.pop_back();
    1.55      }
    1.56 @@ -230,8 +230,8 @@
    1.57        int n = _data.size()-1;
    1.58        _iim.set(_data[h].first, POST_HEAP);
    1.59        if( h < n ) {
    1.60 -        if ( bubble_up(h, _data[n]) == h) {
    1.61 -          bubble_down(h, _data[n], n);
    1.62 +        if ( bubbleUp(h, _data[n]) == h) {
    1.63 +          bubbleDown(h, _data[n], n);
    1.64          }
    1.65        }
    1.66        _data.pop_back();
    1.67 @@ -261,10 +261,10 @@
    1.68          push(i,p);
    1.69        }
    1.70        else if( _comp(p, _data[idx].second) ) {
    1.71 -        bubble_up(idx, Pair(i,p));
    1.72 +        bubbleUp(idx, Pair(i,p));
    1.73        }
    1.74        else {
    1.75 -        bubble_down(idx, Pair(i,p), _data.size());
    1.76 +        bubbleDown(idx, Pair(i,p), _data.size());
    1.77        }
    1.78      }
    1.79  
    1.80 @@ -276,7 +276,7 @@
    1.81      /// \pre \e i must be stored in the heap with priority at least \e p.
    1.82      void decrease(const Item &i, const Prio &p) {
    1.83        int idx = _iim[i];
    1.84 -      bubble_up(idx, Pair(i,p));
    1.85 +      bubbleUp(idx, Pair(i,p));
    1.86      }
    1.87  
    1.88      /// \brief Increase the priority of an item to the given value.
    1.89 @@ -287,7 +287,7 @@
    1.90      /// \pre \e i must be stored in the heap with priority at most \e p.
    1.91      void increase(const Item &i, const Prio &p) {
    1.92        int idx = _iim[i];
    1.93 -      bubble_down(idx, Pair(i,p), _data.size());
    1.94 +      bubbleDown(idx, Pair(i,p), _data.size());
    1.95      }
    1.96  
    1.97      /// \brief Return the state of an item.