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