1.1 --- a/lemon/bin_heap.h	Thu Dec 20 15:13:06 2007 +0000
     1.2 +++ b/lemon/bin_heap.h	Thu Dec 20 15:21:22 2007 +0000
     1.3 @@ -120,30 +120,50 @@
     1.4  
     1.5    private:
     1.6      static int parent(int i) { return (i-1)/2; }
     1.7 +
     1.8      static int second_child(int i) { return 2*i+2; }
     1.9      bool less(const PairType &p1, const PairType &p2) const {
    1.10        return comp(p1.second, p2.second);
    1.11      }
    1.12  
    1.13 -    int bubble_up(int hole, PairType p);
    1.14 -    int bubble_down(int hole, PairType p, int length);
    1.15 +    int bubble_up(int hole, PairType p) {
    1.16 +      int par = parent(hole);
    1.17 +      while( hole>0 && less(p,data[par]) ) {
    1.18 +	move(data[par],hole);
    1.19 +	hole = par;
    1.20 +	par = parent(hole);
    1.21 +      }
    1.22 +      move(p, hole);
    1.23 +      return hole;
    1.24 +    }
    1.25 +
    1.26 +    int bubble_down(int hole, PairType p, int length) {
    1.27 +      int child = second_child(hole);
    1.28 +      while(child < length) {
    1.29 +	if( less(data[child-1], data[child]) ) {
    1.30 +	  --child;
    1.31 +	}
    1.32 +	if( !less(data[child], p) )
    1.33 +	  goto ok;
    1.34 +	move(data[child], hole);
    1.35 +	hole = child;
    1.36 +	child = second_child(hole);
    1.37 +      }
    1.38 +      child--;
    1.39 +      if( child<length && less(data[child], p) ) {
    1.40 +	move(data[child], hole);
    1.41 +	hole=child;
    1.42 +      }
    1.43 +    ok:
    1.44 +      move(p, hole);
    1.45 +      return hole;
    1.46 +    }
    1.47  
    1.48      void move(const PairType &p, int i) {
    1.49        data[i] = p;
    1.50        iim.set(p.first, i);
    1.51      }
    1.52  
    1.53 -    void rmidx(int h) {
    1.54 -      int n = data.size()-1;
    1.55 -      if( h>=0 && h<=n ) {
    1.56 -	iim.set(data[h].first, POST_HEAP);
    1.57 -	if ( h<n ) {
    1.58 -	  bubble_down(h, data[n], n);
    1.59 -	}
    1.60 -	data.pop_back();
    1.61 -      }
    1.62 -    }
    1.63 -
    1.64    public:
    1.65      /// \brief Insert a pair of item and priority into the heap.
    1.66      ///
    1.67 @@ -185,16 +205,29 @@
    1.68      /// Compare from the heap.  
    1.69      /// \pre The heap must be non-empty.  
    1.70      void pop() {
    1.71 -      rmidx(0);
    1.72 +      int n = data.size()-1;
    1.73 +      iim.set(data[0].first, POST_HEAP);
    1.74 +      if (n > 0) {
    1.75 +	bubble_down(0, data[n], n);
    1.76 +      }
    1.77 +      data.pop_back();
    1.78      }
    1.79  
    1.80      /// \brief Deletes \c i from the heap.
    1.81      ///
    1.82 -    /// This method deletes item \c i from the heap, if \c i was
    1.83 -    /// already stored in the heap.
    1.84 -    /// \param i The item to erase. 
    1.85 +    /// This method deletes item \c i from the heap.
    1.86 +    /// \param i The item to erase.
    1.87 +    /// \pre The item should be in the heap.
    1.88      void erase(const ItemType &i) {
    1.89 -      rmidx(iim[i]);
    1.90 +      int h = iim[i];
    1.91 +      int n = data.size()-1;
    1.92 +      iim.set(data[h].first, POST_HEAP);
    1.93 +      if( h < n ) {
    1.94 +	if ( bubble_up(h, data[n]) == h) {
    1.95 +	  bubble_down(h, data[n], n);
    1.96 +	}
    1.97 +      }
    1.98 +      data.pop_back();
    1.99      }
   1.100  
   1.101      
   1.102 @@ -289,44 +322,7 @@
   1.103      }
   1.104  
   1.105    }; // class BinHeap
   1.106 -
   1.107    
   1.108 -  template <typename V, typename M, typename C>
   1.109 -  int BinHeap<V,M,C>::bubble_up(int hole, PairType p) {
   1.110 -    int par = parent(hole);
   1.111 -    while( hole>0 && less(p,data[par]) ) {
   1.112 -      move(data[par],hole);
   1.113 -      hole = par;
   1.114 -      par = parent(hole);
   1.115 -    }
   1.116 -    move(p, hole);
   1.117 -    return hole;
   1.118 -  }
   1.119 -
   1.120 -  template <typename V, typename M, typename C>
   1.121 -  int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) {
   1.122 -    int child = second_child(hole);
   1.123 -    while(child < length) {
   1.124 -      if( less(data[child-1], data[child]) ) {
   1.125 -	--child;
   1.126 -      }
   1.127 -      if( !less(data[child], p) )
   1.128 -	goto ok;
   1.129 -      move(data[child], hole);
   1.130 -      hole = child;
   1.131 -      child = second_child(hole);
   1.132 -    }
   1.133 -    child--;
   1.134 -    if( child<length && less(data[child], p) ) {
   1.135 -      move(data[child], hole);
   1.136 -      hole=child;
   1.137 -    }
   1.138 -  ok:
   1.139 -    move(p, hole);
   1.140 -    return hole;
   1.141 -  }
   1.142 -
   1.143 -
   1.144  } // namespace lemon
   1.145  
   1.146  #endif // LEMON_BIN_HEAP_H