Changeset 756:0747f332c478 in lemon for lemon/fib_heap.h
 Timestamp:
 07/08/09 17:21:30 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/fib_heap.h
r730 r756 22 22 ///\file 23 23 ///\ingroup auxdat 24 ///\brief Fibonacci Heap implementation.24 ///\brief Fibonacci heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 32 33 /// \ingroup auxdat 33 34 /// 34 /// \brief Fibonacci Heap.35 /// \brief Fibonacci heap data structure. 35 36 /// 36 ///This class implements the \e Fibonacci \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 CMP specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 37 /// This class implements the \e Fibonacci \e heap data structure. 38 /// It fully conforms to the \ref concepts::Heap "heap concept". 41 39 /// 42 /// The methods \ref increase and \ref erase are not efficient in a Fibonacci43 /// heap. In case of many calls to these operations, it is better to use a44 /// \ref BinHeap "binary heap".40 /// The methods \ref increase() and \ref erase() are not efficient in a 41 /// Fibonacci heap. In case of many calls of these operations, it is 42 /// better to use other heap structure, e.g. \ref BinHeap "binary heap". 45 43 /// 46 ///\param PRIO Type of the priority of the items. 47 ///\param IM A read and writable Item int map, used internally 48 ///to handle the cross references. 49 ///\param CMP A class for the ordering of the priorities. The 50 ///default is \c std::less<PRIO>. 51 /// 52 ///\sa BinHeap 53 ///\sa Dijkstra 44 /// \tparam PR Type of the priorities of the items. 45 /// \tparam IM A readwritable item map with \c int values, used 46 /// internally to handle the cross references. 47 /// \tparam CMP A functor class for comparing the priorities. 48 /// The default is \c std::less<PR>. 54 49 #ifdef DOXYGEN 55 template <typename PR IO, typename IM, typename CMP>50 template <typename PR, typename IM, typename CMP> 56 51 #else 57 template <typename PR IO, typename IM, typename CMP = std::less<PRIO> >52 template <typename PR, typename IM, typename CMP = std::less<PR> > 58 53 #endif 59 54 class FibHeap { 60 55 public: 61 ///\e 56 57 /// Type of the itemint map. 62 58 typedef IM ItemIntMap; 63 /// \e64 typedef PR IOPrio;65 /// \e59 /// Type of the priorities. 60 typedef PR Prio; 61 /// Type of the items stored in the heap. 66 62 typedef typename ItemIntMap::Key Item; 67 /// \e63 /// Type of the itempriority pairs. 68 64 typedef std::pair<Item,Prio> Pair; 69 /// \e65 /// Functor type for comparing the priorities. 70 66 typedef CMP Compare; 71 67 … … 81 77 public: 82 78 83 /// \brief Type to represent the items states.84 /// 85 /// Each Item element have a state associated to it. It maybe "in heap",86 /// "pre heap" or "postheap". The latter two are indifferent from the79 /// \brief Type to represent the states of the items. 80 /// 81 /// Each item has a state associated to it. It can be "in heap", 82 /// "preheap" or "postheap". The latter two are indifferent from the 87 83 /// heap's point of view, but may be useful to the user. 88 84 /// … … 95 91 }; 96 92 97 /// \brief The constructor 98 /// 99 /// \c map should be given to the constructor, since it is 100 /// used internally to handle the cross references. 93 /// \brief Constructor. 94 /// 95 /// Constructor. 96 /// \param map A map that assigns \c int values to the items. 97 /// It is used internally to handle the cross references. 98 /// The assigned value must be \c PRE_HEAP (<tt>1</tt>) for each item. 101 99 explicit FibHeap(ItemIntMap &map) 102 100 : _minimum(0), _iim(map), _num() {} 103 101 104 /// \brief The constructor 105 /// 106 /// \c map should be given to the constructor, since it is used 107 /// internally to handle the cross references. \c comp is an 108 /// object for ordering of the priorities. 102 /// \brief Constructor. 103 /// 104 /// Constructor. 105 /// \param map A map that assigns \c int values to the items. 106 /// It is used internally to handle the cross references. 107 /// The assigned value must be \c PRE_HEAP (<tt>1</tt>) for each item. 108 /// \param comp The function object used for comparing the priorities. 109 109 FibHeap(ItemIntMap &map, const Compare &comp) 110 110 : _minimum(0), _iim(map), _comp(comp), _num() {} … … 112 112 /// \brief The number of items stored in the heap. 113 113 /// 114 /// Returns the number of items stored in the heap.114 /// This function returns the number of items stored in the heap. 115 115 int size() const { return _num; } 116 116 117 /// \brief Check s if the heap stores no items.118 /// 119 /// Returns \c true if and only if the heap stores no items.117 /// \brief Check if the heap is empty. 118 /// 119 /// This function returns \c true if the heap is empty. 120 120 bool empty() const { return _num==0; } 121 121 122 /// \brief Make empty this heap. 123 /// 124 /// Make empty this heap. It does not change the cross reference 125 /// map. If you want to reuse a heap what is not surely empty you 126 /// should first clear the heap and after that you should set the 127 /// cross reference map for each item to \c PRE_HEAP. 122 /// \brief Make the heap empty. 123 /// 124 /// This functon makes the heap empty. 125 /// It does not change the cross reference map. If you want to reuse 126 /// a heap that is not surely empty, you should first clear it and 127 /// then you should set the cross reference map to \c PRE_HEAP 128 /// for each item. 128 129 void clear() { 129 130 _data.clear(); _minimum = 0; _num = 0; 130 131 } 131 132 132 /// \brief \c item gets to the heap with priority \c value independently 133 /// if \c item was already there. 134 /// 135 /// This method calls \ref push(\c item, \c value) if \c item is not 136 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 137 /// \ref increase(\c item, \c value) otherwise. 138 void set (const Item& item, const Prio& value) { 139 int i=_iim[item]; 140 if ( i >= 0 && _data[i].in ) { 141 if ( _comp(value, _data[i].prio) ) decrease(item, value); 142 if ( _comp(_data[i].prio, value) ) increase(item, value); 143 } else push(item, value); 144 } 145 146 /// \brief Adds \c item to the heap with priority \c value. 147 /// 148 /// Adds \c item to the heap with priority \c value. 149 /// \pre \c item must not be stored in the heap. 150 void push (const Item& item, const Prio& value) { 133 /// \brief Insert an item into the heap with the given priority. 134 /// 135 /// This function inserts the given item into the heap with the 136 /// given priority. 137 /// \param item The item to insert. 138 /// \param prio The priority of the item. 139 /// \pre \e item must not be stored in the heap. 140 void push (const Item& item, const Prio& prio) { 151 141 int i=_iim[item]; 152 142 if ( i < 0 ) { … … 169 159 _data[_minimum].right_neighbor=i; 170 160 _data[i].left_neighbor=_minimum; 171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i;161 if ( _comp( prio, _data[_minimum].prio) ) _minimum=i; 172 162 } else { 173 163 _data[i].right_neighbor=_data[i].left_neighbor=i; 174 164 _minimum=i; 175 165 } 176 _data[i].prio= value;166 _data[i].prio=prio; 177 167 ++_num; 178 168 } 179 169 180 /// \brief Returns the item with minimum priority relative to \c Compare. 181 /// 182 /// This method returns the item with minimum priority relative to \c 183 /// Compare. 184 /// \pre The heap must be nonempty. 170 /// \brief Return the item having minimum priority. 171 /// 172 /// This function returns the item having minimum priority. 173 /// \pre The heap must be nonempty. 185 174 Item top() const { return _data[_minimum].name; } 186 175 187 /// \brief Returns the minimum priority relative to \c Compare. 188 /// 189 /// It returns the minimum priority relative to \c Compare. 190 /// \pre The heap must be nonempty. 191 const Prio& prio() const { return _data[_minimum].prio; } 192 193 /// \brief Returns the priority of \c item. 194 /// 195 /// It returns the priority of \c item. 196 /// \pre \c item must be in the heap. 197 const Prio& operator[](const Item& item) const { 198 return _data[_iim[item]].prio; 199 } 200 201 /// \brief Deletes the item with minimum priority relative to \c Compare. 202 /// 203 /// This method deletes the item with minimum priority relative to \c 204 /// Compare from the heap. 176 /// \brief The minimum priority. 177 /// 178 /// This function returns the minimum priority. 179 /// \pre The heap must be nonempty. 180 Prio prio() const { return _data[_minimum].prio; } 181 182 /// \brief Remove the item having minimum priority. 183 /// 184 /// This function removes the item having minimum priority. 205 185 /// \pre The heap must be nonempty. 206 186 void pop() { … … 235 215 } 236 216 237 /// \brief Deletes \c item from the heap. 238 /// 239 /// This method deletes \c item from the heap, if \c item was already 240 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 217 /// \brief Remove the given item from the heap. 218 /// 219 /// This function removes the given item from the heap if it is 220 /// already stored. 221 /// \param item The item to delete. 222 /// \pre \e item must be in the heap. 241 223 void erase (const Item& item) { 242 224 int i=_iim[item]; … … 253 235 } 254 236 255 /// \brief Decreases the priority of \c item to \c value. 256 /// 257 /// This method decreases the priority of \c item to \c value. 258 /// \pre \c item must be stored in the heap with priority at least \c 259 /// value relative to \c Compare. 260 void decrease (Item item, const Prio& value) { 237 /// \brief The priority of the given item. 238 /// 239 /// This function returns the priority of the given item. 240 /// \param item The item. 241 /// \pre \e item must be in the heap. 242 Prio operator[](const Item& item) const { 243 return _data[_iim[item]].prio; 244 } 245 246 /// \brief Set the priority of an item or insert it, if it is 247 /// not stored in the heap. 248 /// 249 /// This method sets the priority of the given item if it is 250 /// already stored in the heap. Otherwise it inserts the given 251 /// item into the heap with the given priority. 252 /// \param item The item. 253 /// \param prio The priority. 254 void set (const Item& item, const Prio& prio) { 261 255 int i=_iim[item]; 262 _data[i].prio=value; 256 if ( i >= 0 && _data[i].in ) { 257 if ( _comp(prio, _data[i].prio) ) decrease(item, prio); 258 if ( _comp(_data[i].prio, prio) ) increase(item, prio); 259 } else push(item, prio); 260 } 261 262 /// \brief Decrease the priority of an item to the given value. 263 /// 264 /// This function decreases the priority of an item to the given value. 265 /// \param item The item. 266 /// \param prio The priority. 267 /// \pre \e item must be stored in the heap with priority at least \e prio. 268 void decrease (const Item& item, const Prio& prio) { 269 int i=_iim[item]; 270 _data[i].prio=prio; 263 271 int p=_data[i].parent; 264 272 265 if ( p!=1 && _comp( value, _data[p].prio) ) {273 if ( p!=1 && _comp(prio, _data[p].prio) ) { 266 274 cut(i,p); 267 275 cascade(p); 268 276 } 269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 270 } 271 272 /// \brief Increases the priority of \c item to \c value. 273 /// 274 /// This method sets the priority of \c item to \c value. Though 275 /// there is no precondition on the priority of \c item, this 276 /// method should be used only if it is indeed necessary to increase 277 /// (relative to \c Compare) the priority of \c item, because this 278 /// method is inefficient. 279 void increase (Item item, const Prio& value) { 277 if ( _comp(prio, _data[_minimum].prio) ) _minimum=i; 278 } 279 280 /// \brief Increase the priority of an item to the given value. 281 /// 282 /// This function increases the priority of an item to the given value. 283 /// \param item The item. 284 /// \param prio The priority. 285 /// \pre \e item must be stored in the heap with priority at most \e prio. 286 void increase (const Item& item, const Prio& prio) { 280 287 erase(item); 281 push(item, value);282 } 283 284 285 /// \brief Returns if \c item is in, has already been in, or has never286 /// been in the heap.287 /// 288 /// This method returns PRE_HEAP if \c item has never been in the289 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP290 /// otherwise. In the latter case it is possible that \c item will291 /// get back to the heap again.288 push(item, prio); 289 } 290 291 /// \brief Return the state of an item. 292 /// 293 /// This method returns \c PRE_HEAP if the given item has never 294 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 295 /// and \c POST_HEAP otherwise. 296 /// In the latter case it is possible that the item will get back 297 /// to the heap again. 298 /// \param item The item. 292 299 State state(const Item &item) const { 293 300 int i=_iim[item]; … … 299 306 } 300 307 301 /// \brief Set s the state of the \citem in the heap.302 /// 303 /// Sets the state of the \c item in the heap. It can be used to304 /// manually clear the heap when it is important to achive the305 /// better time _complexity.308 /// \brief Set the state of an item in the heap. 309 /// 310 /// This function sets the state of the given item in the heap. 311 /// It can be used to manually clear the heap when it is important 312 /// to achive better time complexity. 306 313 /// \param i The item. 307 314 /// \param st The state. It should not be \c IN_HEAP.
Note: See TracChangeset
for help on using the changeset viewer.