Port max. card. search alg. from svn -r3512 (#397) and (#56)
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2009
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.
29 #include <lemon/math.h>
35 ///\brief Pairing Heap.
37 /// This class implements the \e pairing \e heap data structure.
38 /// It fully conforms to the \ref concepts::Heap "heap concept".
40 /// The methods \ref increase() and \ref erase() are not efficient
41 /// in a pairing heap. In case of many calls of these operations,
42 /// it is better to use other heap structure, e.g. \ref BinHeap
45 /// \tparam PR Type of the priorities of the items.
46 /// \tparam IM A read-writable item map with \c int values, used
47 /// internally to handle the cross references.
48 /// \tparam CMP A functor class for comparing the priorities.
49 /// The default is \c std::less<PR>.
51 template <typename PR, typename IM, typename CMP>
53 template <typename PR, typename IM, typename CMP = std::less<PR> >
57 /// Type of the item-int map.
58 typedef IM ItemIntMap;
59 /// Type of the priorities.
61 /// Type of the items stored in the heap.
62 typedef typename ItemIntMap::Key Item;
63 /// Functor type for comparing the priorities.
66 /// \brief Type to represent the states of the items.
68 /// Each item has a state associated to it. It can be "in heap",
69 /// "pre-heap" or "post-heap". The latter two are indifferent from the
70 /// heap's point of view, but may be useful to the user.
72 /// The item-int map must be initialized in such way that it assigns
73 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
75 IN_HEAP = 0, ///< = 0.
76 PRE_HEAP = -1, ///< = -1.
77 POST_HEAP = -2 ///< = -2.
83 std::vector<store> _data;
90 /// \brief Constructor.
93 /// \param map A map that assigns \c int values to the items.
94 /// It is used internally to handle the cross references.
95 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
96 explicit PairingHeap(ItemIntMap &map)
97 : _min(0), _iim(map), _num_items(0) {}
99 /// \brief Constructor.
102 /// \param map A map that assigns \c int values to the items.
103 /// It is used internally to handle the cross references.
104 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
105 /// \param comp The function object used for comparing the priorities.
106 PairingHeap(ItemIntMap &map, const Compare &comp)
107 : _min(0), _iim(map), _comp(comp), _num_items(0) {}
109 /// \brief The number of items stored in the heap.
111 /// This function returns the number of items stored in the heap.
112 int size() const { return _num_items; }
114 /// \brief Check if the heap is empty.
116 /// This function returns \c true if the heap is empty.
117 bool empty() const { return _num_items==0; }
119 /// \brief Make the heap empty.
121 /// This functon makes the heap empty.
122 /// It does not change the cross reference map. If you want to reuse
123 /// a heap that is not surely empty, you should first clear it and
124 /// then you should set the cross reference map to \c PRE_HEAP
132 /// \brief Set the priority of an item or insert it, if it is
133 /// not stored in the heap.
135 /// This method sets the priority of the given item if it is
136 /// already stored in the heap. Otherwise it inserts the given
137 /// item into the heap with the given priority.
138 /// \param item The item.
139 /// \param value The priority.
140 void set (const Item& item, const Prio& value) {
142 if ( i>=0 && _data[i].in ) {
143 if ( _comp(value, _data[i].prio) ) decrease(item, value);
144 if ( _comp(_data[i].prio, value) ) increase(item, value);
145 } else push(item, value);
148 /// \brief Insert an item into the heap with the given priority.
150 /// This function inserts the given item into the heap with the
152 /// \param item The item to insert.
153 /// \param value The priority of the item.
154 /// \pre \e item must not be stored in the heap.
155 void push (const Item& item, const Prio& value) {
165 _data[i].parent=_data[i].child=-1;
166 _data[i].left_child=false;
173 if ( _num_items!=0 ) {
174 if ( _comp( value, _data[_min].prio) ) {
185 /// \brief Return the item having minimum priority.
187 /// This function returns the item having minimum priority.
188 /// \pre The heap must be non-empty.
189 Item top() const { return _data[_min].name; }
191 /// \brief The minimum priority.
193 /// This function returns the minimum priority.
194 /// \pre The heap must be non-empty.
195 const Prio& prio() const { return _data[_min].prio; }
197 /// \brief The priority of the given item.
199 /// This function returns the priority of the given item.
200 /// \param item The item.
201 /// \pre \e item must be in the heap.
202 const Prio& operator[](const Item& item) const {
203 return _data[_iim[item]].prio;
206 /// \brief Remove the item having minimum priority.
208 /// This function removes the item having minimum priority.
209 /// \pre The heap must be non-empty.
211 std::vector<int> trees;
212 int i=0, child_right = 0;
213 _data[_min].in=false;
215 if( -1!=_data[_min].child ) {
218 _data[i].parent = -1;
219 _data[_min].child = -1;
222 while( _data[i].child!=-1 ) {
224 if( _data[ch].left_child && i==_data[ch].parent ) {
227 if( _data[ch].left_child ) {
228 child_right=_data[ch].parent;
229 _data[ch].parent = i;
237 _data[child_right].parent = -1;
238 trees.push_back(child_right);
243 int num_child = trees.size();
245 for( i=0; i<num_child-1; i+=2 ) {
246 if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) {
251 fuse( trees[i], trees[i+1] );
254 i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
256 if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) {
261 fuse( trees[i-2], trees[i] );
267 _min = _data[_min].child;
270 if (_min >= 0) _data[_min].left_child = false;
274 /// \brief Remove the given item from the heap.
276 /// This function removes the given item from the heap if it is
278 /// \param item The item to delete.
279 /// \pre \e item must be in the heap.
280 void erase (const Item& item) {
282 if ( i>=0 && _data[i].in ) {
283 decrease( item, _data[_min].prio-1 );
288 /// \brief Decrease the priority of an item to the given value.
290 /// This function decreases the priority of an item to the given value.
291 /// \param item The item.
292 /// \param value The priority.
293 /// \pre \e item must be stored in the heap with priority at least \e value.
294 void decrease (Item item, const Prio& value) {
297 int p=_data[i].parent;
299 if( _data[i].left_child && i!=_data[p].child ) {
303 if ( p!=-1 && _comp(value,_data[p].prio) ) {
305 if ( _comp(_data[_min].prio,value) ) {
314 /// \brief Increase the priority of an item to the given value.
316 /// This function increases the priority of an item to the given value.
317 /// \param item The item.
318 /// \param value The priority.
319 /// \pre \e item must be stored in the heap with priority at most \e value.
320 void increase (Item item, const Prio& value) {
325 /// \brief Return the state of an item.
327 /// This method returns \c PRE_HEAP if the given item has never
328 /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
329 /// and \c POST_HEAP otherwise.
330 /// In the latter case it is possible that the item will get back
331 /// to the heap again.
332 /// \param item The item.
333 State state(const Item &item) const {
336 if( _data[i].in ) i=0;
342 /// \brief Set the state of an item in the heap.
344 /// This function sets the state of the given item in the heap.
345 /// It can be used to manually clear the heap when it is important
346 /// to achive better time complexity.
347 /// \param i The item.
348 /// \param st The state. It should not be \c IN_HEAP.
349 void state(const Item& i, State st) {
353 if (state(i) == IN_HEAP) erase(i);
363 void cut(int a, int b) {
365 switch (_data[a].degree) {
367 child_a = _data[_data[a].child].parent;
368 if( _data[a].left_child ) {
369 _data[child_a].left_child=true;
370 _data[b].child=child_a;
371 _data[child_a].parent=_data[a].parent;
374 _data[child_a].left_child=false;
375 _data[child_a].parent=b;
376 if( a!=_data[b].child )
377 _data[_data[b].child].parent=child_a;
379 _data[b].child=child_a;
382 _data[_data[a].child].parent=a;
386 child_a = _data[a].child;
387 if( !_data[child_a].left_child ) {
389 if( _data[a].left_child ) {
390 _data[child_a].left_child=true;
391 _data[child_a].parent=_data[a].parent;
392 _data[b].child=child_a;
395 _data[child_a].left_child=false;
396 _data[child_a].parent=b;
397 if( a!=_data[b].child )
398 _data[_data[b].child].parent=child_a;
400 _data[b].child=child_a;
406 if( _data[a].left_child ) {
408 (1==_data[b].degree) ? _data[a].parent : -1;
410 if (1==_data[b].degree)
411 _data[_data[b].child].parent=b;
420 if( _data[a].left_child ) {
422 (0!=_data[b].degree) ? _data[a].parent : -1;
424 if( 0!=_data[b].degree )
425 _data[_data[b].child].parent=b;
432 _data[a].left_child=false;
435 void fuse(int a, int b) {
436 int child_a = _data[a].child;
437 int child_b = _data[b].child;
440 _data[b].left_child=true;
443 _data[b].child=child_a;
444 _data[child_a].parent=b;
445 _data[child_a].left_child=false;
449 _data[b].child=child_b;
450 _data[child_b].parent=child_a;
453 else { ++_data[a].degree; }
457 friend class PairingHeap;
467 store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
473 #endif //LEMON_PAIRING_HEAP_H