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
Ignore white space 12 line context
... ... 
@@ -42,21 +42,26 @@
42 42 
  /// \ref BinHeap and \ref FouraryHeap are specialized implementations
43 43 
  /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively.
44 44 
  ///
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:
60 65 
    /// Type of the item-int map.
61 66 
    typedef IM ItemIntMap;
62 67 
    /// Type of the priorities.
... ... 
@@ -83,32 +88,31 @@
83 88 
    };
84 89 

			




	85
	90
	
		
  private:


			




	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.


			




	93
	97
	
		
    ///


			




	94
	98
	
		
    /// Constructor.


			




	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
	
		
    ///


			




	102
	106
	
		
    /// Constructor.


			




	103
	107
	
		
    /// \param map A map that assigns \c int values to the items.


			




	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
	
		
    ///


			




	112
	116
	
		
    /// This function returns the number of items stored in the heap.


			




	113
	117
	
		
    int size() const { return _data.size(); }


			




	114
	118
	
		

			




	...
	...
	
		
@@ -124,22 +128,22 @@


			




	124
	128
	
		
    /// a heap that is not surely empty, you should first clear it and


			




	125
	129
	
		
    /// then you should set the cross reference map to \c PRE_HEAP


			




	126
	130
	
		
    /// for each item.


			




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


			




	135
	139
	
		
    }


			




	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;


			




	143
	147
	
		
      }


			




	144
	148
	
		
      return min;


			




	145
	149
	
		
    }


			




        

    






    
    



    


    

     
    
0 comments (0 inline)