14 * express or implied, and with no claim as to its suitability for any |
14 * express or implied, and with no claim as to its suitability for any |
15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #ifndef LEMON_KARY_HEAP_H |
19 #ifndef LEMON_DHEAP_H |
20 #define LEMON_KARY_HEAP_H |
20 #define LEMON_DHEAP_H |
21 |
21 |
22 ///\ingroup heaps |
22 ///\ingroup heaps |
23 ///\file |
23 ///\file |
24 ///\brief Fourary heap implementation. |
24 ///\brief D-ary heap implementation. |
25 |
25 |
26 #include <vector> |
26 #include <vector> |
27 #include <utility> |
27 #include <utility> |
28 #include <functional> |
28 #include <functional> |
29 |
29 |
30 namespace lemon { |
30 namespace lemon { |
31 |
31 |
32 /// \ingroup heaps |
32 /// \ingroup heaps |
33 /// |
33 /// |
34 ///\brief K-ary heap data structure. |
34 ///\brief D-ary heap data structure. |
35 /// |
35 /// |
36 /// This class implements the \e K-ary \e heap data structure. |
36 /// This class implements the \e D-ary \e heap data structure. |
37 /// It fully conforms to the \ref concepts::Heap "heap concept". |
37 /// It fully conforms to the \ref concepts::Heap "heap concept". |
38 /// |
38 /// |
39 /// The \ref KaryHeap "K-ary heap" is a generalization of the |
39 /// The \ref DHeap "D-ary heap" is a generalization of the |
40 /// \ref BinHeap "binary heap" structure, its nodes have at most |
40 /// \ref BinHeap "binary heap" structure, its nodes have at most |
41 /// \c K children, instead of two. |
41 /// \c D children, instead of two. |
42 /// \ref BinHeap and \ref FouraryHeap are specialized implementations |
42 /// \ref BinHeap and \ref QuadHeap are specialized implementations |
43 /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively. |
43 /// of this structure for <tt>D=2</tt> and <tt>D=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 |
48 /// \tparam D The degree of the heap, each node have at most \e D |
49 /// children. The default is 16. Powers of two are suggested to use |
49 /// children. The default is 16. Powers of two are suggested to use |
50 /// so that the multiplications and divisions needed to traverse the |
50 /// so that the multiplications and divisions needed to traverse the |
51 /// nodes of the heap could be performed faster. |
51 /// nodes of the heap could be performed faster. |
52 /// \tparam CMP A functor class for comparing the priorities. |
52 /// \tparam CMP A functor class for comparing the priorities. |
53 /// The default is \c std::less<PR>. |
53 /// The default is \c std::less<PR>. |
54 /// |
54 /// |
55 ///\sa BinHeap |
55 ///\sa BinHeap |
56 ///\sa FouraryHeap |
56 ///\sa FouraryHeap |
57 #ifdef DOXYGEN |
57 #ifdef DOXYGEN |
58 template <typename PR, typename IM, int K, typename CMP> |
58 template <typename PR, typename IM, int D, typename CMP> |
59 #else |
59 #else |
60 template <typename PR, typename IM, int K = 16, |
60 template <typename PR, typename IM, int D = 16, |
61 typename CMP = std::less<PR> > |
61 typename CMP = std::less<PR> > |
62 #endif |
62 #endif |
63 class KaryHeap { |
63 class DHeap { |
64 public: |
64 public: |
65 /// Type of the item-int map. |
65 /// Type of the item-int map. |
66 typedef IM ItemIntMap; |
66 typedef IM ItemIntMap; |
67 /// Type of the priorities. |
67 /// Type of the priorities. |
68 typedef PR Prio; |
68 typedef PR Prio; |
97 /// |
97 /// |
98 /// Constructor. |
98 /// Constructor. |
99 /// \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. |
100 /// It is used internally to handle the cross references. |
100 /// It is used internally to handle the cross references. |
101 /// 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. |
102 explicit KaryHeap(ItemIntMap &map) : _iim(map) {} |
102 explicit DHeap(ItemIntMap &map) : _iim(map) {} |
103 |
103 |
104 /// \brief Constructor. |
104 /// \brief Constructor. |
105 /// |
105 /// |
106 /// Constructor. |
106 /// Constructor. |
107 /// \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. |
108 /// It is used internally to handle the cross references. |
108 /// It is used internally to handle the cross references. |
109 /// 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. |
110 /// \param comp The function object used for comparing the priorities. |
110 /// \param comp The function object used for comparing the priorities. |
111 KaryHeap(ItemIntMap &map, const Compare &comp) |
111 DHeap(ItemIntMap &map, const Compare &comp) |
112 : _iim(map), _comp(comp) {} |
112 : _iim(map), _comp(comp) {} |
113 |
113 |
114 /// \brief The number of items stored in the heap. |
114 /// \brief The number of items stored in the heap. |
115 /// |
115 /// |
116 /// This function returns the number of items stored in the heap. |
116 /// This function returns the number of items stored in the heap. |
129 /// 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 |
130 /// for each item. |
130 /// for each item. |
131 void clear() { _data.clear(); } |
131 void clear() { _data.clear(); } |
132 |
132 |
133 private: |
133 private: |
134 int parent(int i) { return (i-1)/K; } |
134 int parent(int i) { return (i-1)/D; } |
135 int firstChild(int i) { return K*i+1; } |
135 int firstChild(int i) { return D*i+1; } |
136 |
136 |
137 bool less(const Pair &p1, const Pair &p2) const { |
137 bool less(const Pair &p1, const Pair &p2) const { |
138 return _comp(p1.second, p2.second); |
138 return _comp(p1.second, p2.second); |
139 } |
139 } |
140 |
140 |
149 } |
149 } |
150 |
150 |
151 void bubbleDown(int hole, Pair p, int length) { |
151 void bubbleDown(int hole, Pair p, int length) { |
152 if( length>1 ) { |
152 if( length>1 ) { |
153 int child = firstChild(hole); |
153 int child = firstChild(hole); |
154 while( child+K<=length ) { |
154 while( child+D<=length ) { |
155 int min=child; |
155 int min=child; |
156 for (int i=1; i<K; ++i) { |
156 for (int i=1; i<D; ++i) { |
157 if( less(_data[child+i], _data[min]) ) |
157 if( less(_data[child+i], _data[min]) ) |
158 min=child+i; |
158 min=child+i; |
159 } |
159 } |
160 if( !less(_data[min], p) ) |
160 if( !less(_data[min], p) ) |
161 goto ok; |
161 goto ok; |