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
... ... 
@@ -47,2 +47,6 @@
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.
... ... 
@@ -53,5 +57,6 @@
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
... ... 
@@ -88,3 +93,2 @@
88 93 
    ItemIntMap &_iim;
89 
    int _K;
90 94 

			




	...
	...
	
		
@@ -97,3 +101,3 @@


			




	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
	
		

			




	...
	...
	
		
@@ -106,4 +110,4 @@


			




	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
	
		

			




	...
	...
	
		
@@ -129,4 +133,4 @@


			




	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
	
		

			




	...
	...
	
		
@@ -138,3 +142,3 @@


			




	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]) )


			




        

    






    
    



    


    

     
    
0 comments (0 inline)