Changeset 751:7124b2581f72 in lemon for lemon/kary_heap.h
 Timestamp:
 07/10/09 09:15:22 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/kary_heap.h
r750 r751 46 46 /// \tparam IM A readwritable item map with \c int values, used 47 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 52 /// \tparam CMP A functor class for comparing the priorities. 49 53 /// The default is \c std::less<PR>. … … 52 56 ///\sa FouraryHeap 53 57 #ifdef DOXYGEN 54 template <typename PR, typename IM, typename CMP>58 template <typename PR, typename IM, int K, typename CMP> 55 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 62 #endif 58 63 class KaryHeap { … … 87 92 Compare _comp; 88 93 ItemIntMap &_iim; 89 int _K;90 94 91 95 public: … … 96 100 /// It is used internally to handle the cross references. 97 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 104 /// \brief Constructor. … … 105 109 /// The assigned value must be \c PRE_HEAP (<tt>1</tt>) for each item. 106 110 /// \param comp The function object used for comparing the priorities. 107 KaryHeap(ItemIntMap &map, const Compare &comp , int K=32)108 : _iim(map), _comp(comp) , _K(K){}111 KaryHeap(ItemIntMap &map, const Compare &comp) 112 : _iim(map), _comp(comp) {} 109 113 110 114 /// \brief The number of items stored in the heap. … … 128 132 129 133 private: 130 int parent(int i) { return (i1)/ _K; }131 int firstChild(int i) { return _K*i+1; }134 int parent(int i) { return (i1)/K; } 135 int firstChild(int i) { return K*i+1; } 132 136 133 137 bool less(const Pair &p1, const Pair &p2) const { … … 137 141 int findMin(const int child, const int length) { 138 142 int min=child, i=1; 139 while( i< _K && child+i<length ) {143 while( i<K && child+i<length ) { 140 144 if( less(_data[child+i], _data[min]) ) 141 145 min=child+i;
Note: See TracChangeset
for help on using the changeset viewer.