1 /* -*- C++ -*- |
|
2 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 #ifndef LEMON_BIN_HEAP_H |
|
18 #define LEMON_BIN_HEAP_H |
|
19 |
|
20 ///\ingroup auxdat |
|
21 ///\file |
|
22 ///\brief Binary Heap implementation. |
|
23 |
|
24 #include <vector> |
|
25 #include <utility> |
|
26 #include <functional> |
|
27 |
|
28 namespace lemon { |
|
29 |
|
30 /// \addtogroup auxdat |
|
31 /// @{ |
|
32 |
|
33 /// A Binary Heap implementation. |
|
34 |
|
35 ///This class implements the \e binary \e heap data structure. A \e heap |
|
36 ///is a data structure for storing items with specified values called \e |
|
37 ///priorities in such a way that finding the item with minimum priority is |
|
38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
|
39 ///one can change the priority of an item, add or erase an item, etc. |
|
40 /// |
|
41 ///\param Item Type of the items to be stored. |
|
42 ///\param Prio Type of the priority of the items. |
|
43 ///\param ItemIntMap A read and writable Item int map, used internally |
|
44 ///to handle the cross references. |
|
45 ///\param Compare A class for the ordering of the priorities. The |
|
46 ///default is \c std::less<Prio>. |
|
47 /// |
|
48 ///\sa FibHeap |
|
49 ///\sa Dijkstra |
|
50 template <typename Item, typename Prio, typename ItemIntMap, |
|
51 typename Compare = std::less<Prio> > |
|
52 class BinHeap { |
|
53 |
|
54 public: |
|
55 typedef Item ItemType; |
|
56 // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot... |
|
57 typedef Prio PrioType; |
|
58 typedef std::pair<ItemType,PrioType> PairType; |
|
59 typedef ItemIntMap ItemIntMapType; |
|
60 typedef Compare PrioCompare; |
|
61 |
|
62 /// \brief Type to represent the items states. |
|
63 /// |
|
64 /// Each Item element have a state associated to it. It may be "in heap", |
|
65 /// "pre heap" or "post heap". The latter two are indifferent from the |
|
66 /// heap's point of view, but may be useful to the user. |
|
67 /// |
|
68 /// The ItemIntMap \e should be initialized in such way that it maps |
|
69 /// PRE_HEAP (-1) to any element to be put in the heap... |
|
70 enum state_enum { |
|
71 IN_HEAP = 0, |
|
72 PRE_HEAP = -1, |
|
73 POST_HEAP = -2 |
|
74 }; |
|
75 |
|
76 private: |
|
77 std::vector<PairType> data; |
|
78 Compare comp; |
|
79 ItemIntMap &iim; |
|
80 |
|
81 public: |
|
82 /// \brief The constructor. |
|
83 /// |
|
84 /// The constructor. |
|
85 /// \param _iim should be given to the constructor, since it is used |
|
86 /// internally to handle the cross references. The value of the map |
|
87 /// should be PRE_HEAP (-1) for each element. |
|
88 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} |
|
89 |
|
90 /// \brief The constructor. |
|
91 /// |
|
92 /// The constructor. |
|
93 /// \param _iim should be given to the constructor, since it is used |
|
94 /// internally to handle the cross references. The value of the map |
|
95 /// should be PRE_HEAP (-1) for each element. |
|
96 /// |
|
97 /// \param _comp The comparator function object. |
|
98 BinHeap(ItemIntMap &_iim, const Compare &_comp) |
|
99 : iim(_iim), comp(_comp) {} |
|
100 |
|
101 |
|
102 /// The number of items stored in the heap. |
|
103 /// |
|
104 /// \brief Returns the number of items stored in the heap. |
|
105 int size() const { return data.size(); } |
|
106 |
|
107 /// \brief Checks if the heap stores no items. |
|
108 /// |
|
109 /// Returns \c true if and only if the heap stores no items. |
|
110 bool empty() const { return data.empty(); } |
|
111 |
|
112 private: |
|
113 static int parent(int i) { return (i-1)/2; } |
|
114 static int second_child(int i) { return 2*i+2; } |
|
115 bool less(const PairType &p1, const PairType &p2) const { |
|
116 return comp(p1.second, p2.second); |
|
117 } |
|
118 |
|
119 int bubble_up(int hole, PairType p); |
|
120 int bubble_down(int hole, PairType p, int length); |
|
121 |
|
122 void move(const PairType &p, int i) { |
|
123 data[i] = p; |
|
124 iim.set(p.first, i); |
|
125 } |
|
126 |
|
127 void rmidx(int h) { |
|
128 int n = data.size()-1; |
|
129 if( h>=0 && h<=n ) { |
|
130 iim.set(data[h].first, POST_HEAP); |
|
131 if ( h<n ) { |
|
132 bubble_down(h, data[n], n); |
|
133 } |
|
134 data.pop_back(); |
|
135 } |
|
136 } |
|
137 |
|
138 public: |
|
139 /// \brief Insert a pair of item and priority into the heap. |
|
140 /// |
|
141 /// Adds \c p.first to the heap with priority \c p.second. |
|
142 /// \param p The pair to insert. |
|
143 void push(const PairType &p) { |
|
144 int n = data.size(); |
|
145 data.resize(n+1); |
|
146 bubble_up(n, p); |
|
147 } |
|
148 |
|
149 /// \brief Insert an item into the heap with the given heap. |
|
150 /// |
|
151 /// Adds \c i to the heap with priority \c p. |
|
152 /// \param i The item to insert. |
|
153 /// \param p The priority of the item. |
|
154 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } |
|
155 |
|
156 /// \brief Returns the item with minimum priority relative to \c Compare. |
|
157 /// |
|
158 /// This method returns the item with minimum priority relative to \c |
|
159 /// Compare. |
|
160 /// \pre The heap must be nonempty. |
|
161 Item top() const { |
|
162 return data[0].first; |
|
163 } |
|
164 |
|
165 /// \brief Returns the minimum priority relative to \c Compare. |
|
166 /// |
|
167 /// It returns the minimum priority relative to \c Compare. |
|
168 /// \pre The heap must be nonempty. |
|
169 Prio prio() const { |
|
170 return data[0].second; |
|
171 } |
|
172 |
|
173 /// \brief Deletes the item with minimum priority relative to \c Compare. |
|
174 /// |
|
175 /// This method deletes the item with minimum priority relative to \c |
|
176 /// Compare from the heap. |
|
177 /// \pre The heap must be non-empty. |
|
178 void pop() { |
|
179 rmidx(0); |
|
180 } |
|
181 |
|
182 /// \brief Deletes \c i from the heap. |
|
183 /// |
|
184 /// This method deletes item \c i from the heap, if \c i was |
|
185 /// already stored in the heap. |
|
186 /// \param i The item to erase. |
|
187 void erase(const Item &i) { |
|
188 rmidx(iim[i]); |
|
189 } |
|
190 |
|
191 |
|
192 /// \brief Returns the priority of \c i. |
|
193 /// |
|
194 /// This function returns the priority of item \c i. |
|
195 /// \pre \c i must be in the heap. |
|
196 /// \param i The item. |
|
197 Prio operator[](const Item &i) const { |
|
198 int idx = iim[i]; |
|
199 return data[idx].second; |
|
200 } |
|
201 |
|
202 /// \brief \c i gets to the heap with priority \c p independently |
|
203 /// if \c i was already there. |
|
204 /// |
|
205 /// This method calls \ref push(\c i, \c p) if \c i is not stored |
|
206 /// in the heap and sets the priority of \c i to \c p otherwise. |
|
207 /// \param i The item. |
|
208 /// \param p The priority. |
|
209 void set(const Item &i, const Prio &p) { |
|
210 int idx = iim[i]; |
|
211 if( idx < 0 ) { |
|
212 push(i,p); |
|
213 } |
|
214 else if( comp(p, data[idx].second) ) { |
|
215 bubble_up(idx, PairType(i,p)); |
|
216 } |
|
217 else { |
|
218 bubble_down(idx, PairType(i,p), data.size()); |
|
219 } |
|
220 } |
|
221 |
|
222 /// \brief Decreases the priority of \c i to \c p. |
|
223 |
|
224 /// This method decreases the priority of item \c i to \c p. |
|
225 /// \pre \c i must be stored in the heap with priority at least \c |
|
226 /// p relative to \c Compare. |
|
227 /// \param i The item. |
|
228 /// \param p The priority. |
|
229 void decrease(const Item &i, const Prio &p) { |
|
230 int idx = iim[i]; |
|
231 bubble_up(idx, PairType(i,p)); |
|
232 } |
|
233 |
|
234 /// \brief Increases the priority of \c i to \c p. |
|
235 /// |
|
236 /// This method sets the priority of item \c i to \c p. |
|
237 /// \pre \c i must be stored in the heap with priority at most \c |
|
238 /// p relative to \c Compare. |
|
239 /// \param i The item. |
|
240 /// \param p The priority. |
|
241 void increase(const Item &i, const Prio &p) { |
|
242 int idx = iim[i]; |
|
243 bubble_down(idx, PairType(i,p), data.size()); |
|
244 } |
|
245 |
|
246 /// \brief Returns if \c item is in, has already been in, or has |
|
247 /// never been in the heap. |
|
248 /// |
|
249 /// This method returns PRE_HEAP if \c item has never been in the |
|
250 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
251 /// otherwise. In the latter case it is possible that \c item will |
|
252 /// get back to the heap again. |
|
253 /// \param i The item. |
|
254 state_enum state(const Item &i) const { |
|
255 int s = iim[i]; |
|
256 if( s>=0 ) |
|
257 s=0; |
|
258 return state_enum(s); |
|
259 } |
|
260 |
|
261 }; // class BinHeap |
|
262 |
|
263 |
|
264 template <typename K, typename V, typename M, typename C> |
|
265 int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) { |
|
266 int par = parent(hole); |
|
267 while( hole>0 && less(p,data[par]) ) { |
|
268 move(data[par],hole); |
|
269 hole = par; |
|
270 par = parent(hole); |
|
271 } |
|
272 move(p, hole); |
|
273 return hole; |
|
274 } |
|
275 |
|
276 template <typename K, typename V, typename M, typename C> |
|
277 int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) { |
|
278 int child = second_child(hole); |
|
279 while(child < length) { |
|
280 if( less(data[child-1], data[child]) ) { |
|
281 --child; |
|
282 } |
|
283 if( !less(data[child], p) ) |
|
284 goto ok; |
|
285 move(data[child], hole); |
|
286 hole = child; |
|
287 child = second_child(hole); |
|
288 } |
|
289 child--; |
|
290 if( child<length && less(data[child], p) ) { |
|
291 move(data[child], hole); |
|
292 hole=child; |
|
293 } |
|
294 ok: |
|
295 move(p, hole); |
|
296 return hole; |
|
297 } |
|
298 |
|
299 ///@} |
|
300 |
|
301 } // namespace lemon |
|
302 |
|
303 #endif // LEMON_BIN_HEAP_H |
|