3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_PAIRING_HEAP_H
20 #define LEMON_PAIRING_HEAP_H
24 ///\brief Pairing Heap implementation.
28 #include <lemon/math.h>
34 ///\brief Pairing Heap.
36 ///This class implements the \e Pairing \e heap data structure. A \e heap
37 ///is a data structure for storing items with specified values called \e
38 ///priorities in such a way that finding the item with minimum priority is
39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap
40 ///one can change the priority of an item, add or erase an item, etc.
42 ///The methods \ref increase and \ref erase are not efficient in a Pairing
43 ///heap. In case of many calls to these operations, it is better to use a
44 ///\ref BinHeap "binary heap".
46 ///\param _Prio Type of the priority of the items.
47 ///\param _ItemIntMap A read and writable Item int map, used internally
48 ///to handle the cross references.
49 ///\param _Compare A class for the ordering of the priorities. The
50 ///default is \c std::less<_Prio>.
54 ///\author Dorian Batha
57 template <typename _Prio,
61 template <typename _Prio,
63 typename _Compare = std::less<_Prio> >
67 typedef _ItemIntMap ItemIntMap;
69 typedef typename ItemIntMap::Key Item;
70 typedef std::pair<Item,Prio> Pair;
71 typedef _Compare Compare;
76 std::vector<store> container;
83 ///Status of the nodes
85 ///The node is in the heap
87 ///The node has never been in the heap
89 ///The node was in the heap but it got out of it
93 /// \brief The constructor
95 /// \c _iimap should be given to the constructor, since it is
96 /// used internally to handle the cross references.
97 explicit PairingHeap(ItemIntMap &_iimap)
98 : minimum(0), iimap(_iimap), num_items(0) {}
100 /// \brief The constructor
102 /// \c _iimap should be given to the constructor, since it is used
103 /// internally to handle the cross references. \c _comp is an
104 /// object for ordering of the priorities.
105 PairingHeap(ItemIntMap &_iimap, const Compare &_comp)
106 : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {}
108 /// \brief The number of items stored in the heap.
110 /// Returns the number of items stored in the heap.
111 int size() const { return num_items; }
113 /// \brief Checks if the heap stores no items.
115 /// Returns \c true if and only if the heap stores no items.
116 bool empty() const { return num_items==0; }
118 /// \brief Make empty this heap.
120 /// Make empty this heap. It does not change the cross reference
121 /// map. If you want to reuse a heap what is not surely empty you
122 /// should first clear the heap and after that you should set the
123 /// cross reference map for each item to \c PRE_HEAP.
130 /// \brief \c item gets to the heap with priority \c value independently
131 /// if \c item was already there.
133 /// This method calls \ref push(\c item, \c value) if \c item is not
134 /// stored in the heap and it calls \ref decrease(\c item, \c value) or
135 /// \ref increase(\c item, \c value) otherwise.
136 void set (const Item& item, const Prio& value) {
138 if ( i>=0 && container[i].in ) {
139 if ( comp(value, container[i].prio) ) decrease(item, value);
140 if ( comp(container[i].prio, value) ) increase(item, value);
141 } else push(item, value);
144 /// \brief Adds \c item to the heap with priority \c value.
146 /// Adds \c item to the heap with priority \c value.
147 /// \pre \c item must not be stored in the heap.
148 void push (const Item& item, const Prio& value) {
151 int s=container.size();
155 container.push_back(st);
158 container[i].parent=container[i].child=-1;
159 container[i].left_child=false;
160 container[i].degree=0;
161 container[i].in=true;
164 container[i].prio=value;
166 if ( num_items!=0 ) {
167 if ( comp( value, container[minimum].prio) ) {
171 else fuse(minimum,i);
178 /// \brief Returns the item with minimum priority relative to \c Compare.
180 /// This method returns the item with minimum priority relative to \c
182 /// \pre The heap must be nonempty.
183 Item top() const { return container[minimum].name; }
185 /// \brief Returns the minimum priority relative to \c Compare.
187 /// It returns the minimum priority relative to \c Compare.
188 /// \pre The heap must be nonempty.
189 const Prio& prio() const { return container[minimum].prio; }
191 /// \brief Returns the priority of \c item.
193 /// It returns the priority of \c item.
194 /// \pre \c item must be in the heap.
195 const Prio& operator[](const Item& item) const {
196 return container[iimap[item]].prio;
199 /// \brief Deletes the item with minimum priority relative to \c Compare.
201 /// This method deletes the item with minimum priority relative to \c
202 /// Compare from the heap.
203 /// \pre The heap must be non-empty.
205 int TreeArray[num_items];
206 int i=0, num_child=0, child_right = 0;
207 container[minimum].in=false;
209 if( -1!=container[minimum].child ) {
210 i=container[minimum].child;
211 TreeArray[num_child] = i;
212 container[i].parent = -1;
213 container[minimum].child = -1;
217 while( container[i].child!=-1 ) {
218 ch=container[i].child;
219 if( container[ch].left_child && i==container[ch].parent ) {
223 if( container[ch].left_child ) {
224 child_right=container[ch].parent;
225 container[ch].parent = i;
226 --container[i].degree;
230 container[i].child=-1;
231 container[i].degree=0;
233 container[child_right].parent = -1;
234 TreeArray[num_child] = child_right;
241 for( i=0; i<num_child-1; i+=2 ) {
242 if ( !comp(container[TreeArray[i]].prio,
243 container[TreeArray[i+1]].prio) ) {
245 TreeArray[i]=TreeArray[i+1];
246 TreeArray[i+1]=other;
248 fuse( TreeArray[i], TreeArray[i+1] );
251 i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
253 if ( comp(container[TreeArray[i]].prio,
254 container[TreeArray[i-2]].prio) ) {
256 TreeArray[i]=TreeArray[i-2];
257 TreeArray[i-2]=other;
259 fuse( TreeArray[i-2], TreeArray[i] );
262 minimum = TreeArray[0];
265 if ( 0==num_child ) {
266 minimum = container[minimum].child;
272 /// \brief Deletes \c item from the heap.
274 /// This method deletes \c item from the heap, if \c item was already
275 /// stored in the heap. It is quite inefficient in Pairing heaps.
276 void erase (const Item& item) {
278 if ( i>=0 && container[i].in ) {
279 decrease( item, container[minimum].prio-1 );
284 /// \brief Decreases the priority of \c item to \c value.
286 /// This method decreases the priority of \c item to \c value.
287 /// \pre \c item must be stored in the heap with priority at least \c
288 /// value relative to \c Compare.
289 void decrease (Item item, const Prio& value) {
291 container[i].prio=value;
292 int p=container[i].parent;
294 if( container[i].left_child && i!=container[p].child ) {
295 p=container[p].parent;
298 if ( p!=-1 && comp(value,container[p].prio) ) {
300 if ( comp(container[minimum].prio,value) ) {
309 /// \brief Increases the priority of \c item to \c value.
311 /// This method sets the priority of \c item to \c value. Though
312 /// there is no precondition on the priority of \c item, this
313 /// method should be used only if it is indeed necessary to increase
314 /// (relative to \c Compare) the priority of \c item, because this
315 /// method is inefficient.
316 void increase (Item item, const Prio& value) {
321 /// \brief Returns if \c item is in, has already been in, or has never
322 /// been in the heap.
324 /// This method returns PRE_HEAP if \c item has never been in the
325 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
326 /// otherwise. In the latter case it is possible that \c item will
327 /// get back to the heap again.
328 State state(const Item &item) const {
331 if( container[i].in ) i=0;
337 /// \brief Sets the state of the \c item in the heap.
339 /// Sets the state of the \c item in the heap. It can be used to
340 /// manually clear the heap when it is important to achive the
341 /// better time complexity.
342 /// \param i The item.
343 /// \param st The state. It should not be \c IN_HEAP.
344 void state(const Item& i, State st) {
348 if (state(i) == IN_HEAP) erase(i);
358 void cut(int a, int b) {
360 switch (container[a].degree) {
362 child_a = container[container[a].child].parent;
363 if( container[a].left_child ) {
364 container[child_a].left_child=true;
365 container[b].child=child_a;
366 container[child_a].parent=container[a].parent;
369 container[child_a].left_child=false;
370 container[child_a].parent=b;
371 if( a!=container[b].child )
372 container[container[b].child].parent=child_a;
374 container[b].child=child_a;
376 --container[a].degree;
377 container[container[a].child].parent=a;
381 child_a = container[a].child;
382 if( !container[child_a].left_child ) {
383 --container[a].degree;
384 if( container[a].left_child ) {
385 container[child_a].left_child=true;
386 container[child_a].parent=container[a].parent;
387 container[b].child=child_a;
390 container[child_a].left_child=false;
391 container[child_a].parent=b;
392 if( a!=container[b].child )
393 container[container[b].child].parent=child_a;
395 container[b].child=child_a;
397 container[a].child=-1;
400 --container[b].degree;
401 if( container[a].left_child ) {
403 (1==container[b].degree) ? container[a].parent : -1;
405 if (1==container[b].degree)
406 container[container[b].child].parent=b;
408 container[b].child=-1;
414 --container[b].degree;
415 if( container[a].left_child ) {
417 (0!=container[b].degree) ? container[a].parent : -1;
419 if( 0!=container[b].degree )
420 container[container[b].child].parent=b;
422 container[b].child=-1;
426 container[a].parent=-1;
427 container[a].left_child=false;
430 void fuse(int a, int b) {
431 int child_a = container[a].child;
432 int child_b = container[b].child;
433 container[a].child=b;
434 container[b].parent=a;
435 container[b].left_child=true;
438 container[b].child=child_a;
439 container[child_a].parent=b;
440 container[child_a].left_child=false;
441 ++container[b].degree;
444 container[b].child=child_b;
445 container[child_b].parent=child_a;
448 else { ++container[a].degree; }
452 friend class PairingHeap;
462 store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
468 #endif //LEMON_PAIRING_HEAP_H