1.1 --- a/lemon/kary_heap.h	Thu Jul 09 04:07:08 2009 +0200
     1.2 +++ b/lemon/kary_heap.h	Fri Jul 10 09:15:22 2009 +0200
     1.3 @@ -45,15 +45,20 @@
     1.4    /// \tparam PR Type of the priorities of the items.
     1.5    /// \tparam IM A read-writable item map with \c int values, used
     1.6    /// internally to handle the cross references.
     1.7 +  /// \tparam K The degree of the heap, each node have at most \e K
     1.8 +  /// children. The default is 16. Powers of two are suggested to use
     1.9 +  /// so that the multiplications and divisions needed to traverse the
    1.10 +  /// nodes of the heap could be performed faster.
    1.11    /// \tparam CMP A functor class for comparing the priorities.
    1.12    /// The default is \c std::less<PR>.
    1.13    ///
    1.14    ///\sa BinHeap
    1.15    ///\sa FouraryHeap
    1.16  #ifdef DOXYGEN
    1.17 -  template <typename PR, typename IM, typename CMP>
    1.18 +  template <typename PR, typename IM, int K, typename CMP>
    1.19  #else
    1.20 -  template <typename PR, typename IM, typename CMP = std::less<PR> >
    1.21 +  template <typename PR, typename IM, int K = 16,
    1.22 +            typename CMP = std::less<PR> >
    1.23  #endif
    1.24    class KaryHeap {
    1.25    public:
    1.26 @@ -86,7 +91,6 @@
    1.27      std::vector<Pair> _data;
    1.28      Compare _comp;
    1.29      ItemIntMap &_iim;
    1.30 -    int _K;
    1.31  
    1.32    public:
    1.33      /// \brief Constructor.
    1.34 @@ -95,7 +99,7 @@
    1.35      /// \param map A map that assigns \c int values to the items.
    1.36      /// It is used internally to handle the cross references.
    1.37      /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    1.38 -    explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
    1.39 +    explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
    1.40  
    1.41      /// \brief Constructor.
    1.42      ///
    1.43 @@ -104,8 +108,8 @@
    1.44      /// It is used internally to handle the cross references.
    1.45      /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    1.46      /// \param comp The function object used for comparing the priorities.
    1.47 -    KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
    1.48 -      : _iim(map), _comp(comp), _K(K) {}
    1.49 +    KaryHeap(ItemIntMap &map, const Compare &comp)
    1.50 +      : _iim(map), _comp(comp) {}
    1.51  
    1.52      /// \brief The number of items stored in the heap.
    1.53      ///
    1.54 @@ -127,8 +131,8 @@
    1.55      void clear() { _data.clear(); }
    1.56  
    1.57    private:
    1.58 -    int parent(int i) { return (i-1)/_K; }
    1.59 -    int firstChild(int i) { return _K*i+1; }
    1.60 +    int parent(int i) { return (i-1)/K; }
    1.61 +    int firstChild(int i) { return K*i+1; }
    1.62  
    1.63      bool less(const Pair &p1, const Pair &p2) const {
    1.64        return _comp(p1.second, p2.second);
    1.65 @@ -136,7 +140,7 @@
    1.66  
    1.67      int findMin(const int child, const int length) {
    1.68        int min=child, i=1;
    1.69 -      while( i<_K && child+i<length ) {
    1.70 +      while( i<K && child+i<length ) {
    1.71          if( less(_data[child+i], _data[min]) )
    1.72            min=child+i;
    1.73          ++i;