Changeset - r704:7124b2581f72
« 703:bb3392
705:39a5b4 »
gravatar
kpeter (Peter Kovacs)
kpeter@inf.elte.hu
Make K a template parameter in KaryHeap (#301)
0 1 0
default
1 file changed with 13 insertions and 9 deletions:
lemon/kary_heap.h
13
9
↑ Collapse diff ↑
lemon/kary_heap.h
Show white space 6 line context
... ... 
@@ -45,15 +45,20 @@
45 45 
  /// \tparam PR Type of the priorities of the items.
46 46 
  /// \tparam IM A read-writable 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>.
50 54 
  ///
51 55 
  ///\sa BinHeap
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 {
59 64 
  public:
... ... 
@@ -86,7 +91,6 @@
86 91 
    std::vector<Pair> _data;
87 92 
    Compare _comp;
88 93 
    ItemIntMap &_iim;
89 
    int _K;
90 94 

			




	91
	95
	
		
  public:


			




	92
	96
	
		
    /// \brief Constructor.


			




	...
	...
	
		
@@ -95,7 +99,7 @@


			




	95
	99
	
		
    /// \param map A map that assigns \c int values to the items.


			




	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.


			




	101
	105
	
		
    ///


			




	...
	...
	
		
@@ -104,8 +108,8 @@


			




	104
	108
	
		
    /// It is used internally to handle the cross references.


			




	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.


			




	111
	115
	
		
    ///


			




	...
	...
	
		
@@ -127,8 +131,8 @@


			




	127
	131
	
		
    void clear() { _data.clear(); }


			




	128
	132
	
		

			




	129
	133
	
		
  private:


			




	130
	
	
		
    int parent(int i) { return (i-1)/_K; }


			




	131
	
	
		
    int firstChild(int i) { return _K*i+1; }


			




	
	134
	
		
    int parent(int i) { return (i-1)/K; }


			




	
	135
	
		
    int firstChild(int i) { return K*i+1; }


			




	132
	136
	
		

			




	133
	137
	
		
    bool less(const Pair &p1, const Pair &p2) const {


			




	134
	138
	
		
      return _comp(p1.second, p2.second);


			




	...
	...
	
		
@@ -136,7 +140,7 @@


			




	136
	140
	
		

			




	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;


			




	142
	146
	
		
        ++i;


			




        

    






    
    



    


    

     
    
0 comments (0 inline)