lemon/kary_heap.h
changeset 751 7124b2581f72
parent 750 bb3392fe91f2
child 753 9314d9339475
equal deleted inserted replaced
1:3ec8239cd7f1 2:44a3f78187f4
    43   /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
    43   /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
    44   ///
    44   ///
    45   /// \tparam PR Type of the priorities of the items.
    45   /// \tparam PR Type of the priorities of the items.
    46   /// \tparam IM A read-writable item map with \c int values, used
    46   /// \tparam IM A read-writable item map with \c int values, used
    47   /// internally to handle the cross references.
    47   /// internally to handle the cross references.
       
    48   /// \tparam K The degree of the heap, each node have at most \e K
       
    49   /// children. The default is 16. Powers of two are suggested to use
       
    50   /// so that the multiplications and divisions needed to traverse the
       
    51   /// nodes of the heap could be performed faster.
    48   /// \tparam CMP A functor class for comparing the priorities.
    52   /// \tparam CMP A functor class for comparing the priorities.
    49   /// The default is \c std::less<PR>.
    53   /// The default is \c std::less<PR>.
    50   ///
    54   ///
    51   ///\sa BinHeap
    55   ///\sa BinHeap
    52   ///\sa FouraryHeap
    56   ///\sa FouraryHeap
    53 #ifdef DOXYGEN
    57 #ifdef DOXYGEN
    54   template <typename PR, typename IM, typename CMP>
    58   template <typename PR, typename IM, int K, typename CMP>
    55 #else
    59 #else
    56   template <typename PR, typename IM, typename CMP = std::less<PR> >
    60   template <typename PR, typename IM, int K = 16,
       
    61             typename CMP = std::less<PR> >
    57 #endif
    62 #endif
    58   class KaryHeap {
    63   class KaryHeap {
    59   public:
    64   public:
    60     /// Type of the item-int map.
    65     /// Type of the item-int map.
    61     typedef IM ItemIntMap;
    66     typedef IM ItemIntMap;
    84 
    89 
    85   private:
    90   private:
    86     std::vector<Pair> _data;
    91     std::vector<Pair> _data;
    87     Compare _comp;
    92     Compare _comp;
    88     ItemIntMap &_iim;
    93     ItemIntMap &_iim;
    89     int _K;
       
    90 
    94 
    91   public:
    95   public:
    92     /// \brief Constructor.
    96     /// \brief Constructor.
    93     ///
    97     ///
    94     /// Constructor.
    98     /// Constructor.
    95     /// \param map A map that assigns \c int values to the items.
    99     /// \param map A map that assigns \c int values to the items.
    96     /// It is used internally to handle the cross references.
   100     /// It is used internally to handle the cross references.
    97     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   101     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
    98     explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {}
   102     explicit KaryHeap(ItemIntMap &map) : _iim(map) {}
    99 
   103 
   100     /// \brief Constructor.
   104     /// \brief Constructor.
   101     ///
   105     ///
   102     /// Constructor.
   106     /// Constructor.
   103     /// \param map A map that assigns \c int values to the items.
   107     /// \param map A map that assigns \c int values to the items.
   104     /// It is used internally to handle the cross references.
   108     /// It is used internally to handle the cross references.
   105     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   109     /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
   106     /// \param comp The function object used for comparing the priorities.
   110     /// \param comp The function object used for comparing the priorities.
   107     KaryHeap(ItemIntMap &map, const Compare &comp, int K=32)
   111     KaryHeap(ItemIntMap &map, const Compare &comp)
   108       : _iim(map), _comp(comp), _K(K) {}
   112       : _iim(map), _comp(comp) {}
   109 
   113 
   110     /// \brief The number of items stored in the heap.
   114     /// \brief The number of items stored in the heap.
   111     ///
   115     ///
   112     /// This function returns the number of items stored in the heap.
   116     /// This function returns the number of items stored in the heap.
   113     int size() const { return _data.size(); }
   117     int size() const { return _data.size(); }
   125     /// then you should set the cross reference map to \c PRE_HEAP
   129     /// then you should set the cross reference map to \c PRE_HEAP
   126     /// for each item.
   130     /// for each item.
   127     void clear() { _data.clear(); }
   131     void clear() { _data.clear(); }
   128 
   132 
   129   private:
   133   private:
   130     int parent(int i) { return (i-1)/_K; }
   134     int parent(int i) { return (i-1)/K; }
   131     int firstChild(int i) { return _K*i+1; }
   135     int firstChild(int i) { return K*i+1; }
   132 
   136 
   133     bool less(const Pair &p1, const Pair &p2) const {
   137     bool less(const Pair &p1, const Pair &p2) const {
   134       return _comp(p1.second, p2.second);
   138       return _comp(p1.second, p2.second);
   135     }
   139     }
   136 
   140 
   137     int findMin(const int child, const int length) {
   141     int findMin(const int child, const int length) {
   138       int min=child, i=1;
   142       int min=child, i=1;
   139       while( i<_K && child+i<length ) {
   143       while( i<K && child+i<length ) {
   140         if( less(_data[child+i], _data[min]) )
   144         if( less(_data[child+i], _data[min]) )
   141           min=child+i;
   145           min=child+i;
   142         ++i;
   146         ++i;
   143       }
   147       }
   144       return min;
   148       return min;