Changeset 857:4e948fd205f7 in lemon-0.x
- Timestamp:
- 09/15/04 16:04:57 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1157
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/fib_heap.h
r539 r857 4 4 #define HUGO_FIB_HEAP_H 5 5 6 ///\file 6 7 ///\ingroup auxdat 7 ///\file8 8 ///\brief Fibonacci Heap implementation. 9 9 … … 17 17 /// @{ 18 18 19 /// An implementation of the Fibonacci Heap. 20 21 /** 22 This class implements the \e Fibonacci \e heap data structure. A \e heap 23 is a data structure for storing items with specified values called \e 24 priorities, such that finding the item with minimum priority with respect 25 to \e Compare is efficient. In a heap one can change the priority of an 26 item, add or erase an item, etc. 27 28 The methods \ref increase and \ref erase are not efficient in a Fibonacci 29 heap. In case of many calls to these operations, it is better to use a 30 \e binary \e heap. 31 32 \param Item The type of the items to be stored. 33 \param Prio The type of the priority of the items. 34 \param ItemIntMap A read and writable Item int map, for the usage of 35 the heap. 36 \param Compare A class for the comparison of the priorities. The 37 default is \c std::less<Prio>. 38 39 */ 40 19 /// Fibonacci Heap. 20 21 ///This class implements the \e Fibonacci \e heap data structure. A \e heap 22 ///is a data structure for storing items with specified values called \e 23 ///priorities in such a way that finding the item with minimum priority is 24 ///efficient. \ref Compare specifies the ordering of the priorities. In a heap 25 ///one can change the priority of an item, add or erase an item, etc. 26 /// 27 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci 28 ///heap. In case of many calls to these operations, it is better to use a 29 ///\e binary \e heap. 30 /// 31 ///\param Item Type of the items to be stored. 32 ///\param Prio Type of the priority of the items. 33 ///\param ItemIntMap A read and writable Item int map, for the usage of 34 ///the heap. 35 ///\param Compare A class for the ordering of the priorities. The 36 ///default is \c std::less<Prio>. 37 /// 38 ///\author Jacint Szabo 39 41 40 #ifdef DOXYGEN 42 41 template <typename Item, … … 84 83 85 84 /** 86 Returns \c true if f the heap stores no items.85 Returns \c true if and only if the heap stores no items. 87 86 */ 88 87 bool empty() const { return num_items==0; } … … 105 104 void push (Item const item, PrioType const value); 106 105 107 108 ///Returns the item having the minimum priority w.r.t. Compare. 109 110 /** 111 This method returns the item having the minimum priority w.r.t. Compare. 106 ///Returns the item with minimum priority relative to \ref Compare. 107 108 /** 109 This method returns the item with minimum priority relative to \ref 110 Compare. 111 \pre The heap must be nonempty. 112 */ 113 Item top() const { return container[minimum].name; } 114 115 ///Returns the minimum priority relative to \ref Compare. 116 117 /** 118 It returns the minimum priority relative to \ref Compare. 112 119 \pre The heap must be nonempty. 113 120 */ 114 Item top() const { return container[minimum].name; }115 116 117 ///Returns the minimum priority w.r.t. Compare.118 119 /**120 It returns the minimum priority w.r.t. Compare.121 \pre The heap must be nonempty.122 */123 121 PrioType prio() const { return container[minimum].prio; } 124 122 125 126 123 ///Returns the priority of \c item. 127 124 125 /** 126 This function returns the priority of \c item. 127 \pre \c item must be in the heap. 128 */ 129 PrioType& operator[](const Item& item) { 130 return container[iimap[item]].prio; 131 } 132 133 ///Returns the priority of \c item. 134 128 135 /** 129 136 It returns the priority of \c item. 130 137 \pre \c item must be in the heap. 131 138 */ 132 PrioType& operator[](const Item& item) {133 return container[iimap[item]].prio;134 }135 136 ///Returns the priority of \c item.137 138 /**139 It returns the priority of \c item.140 \pre \c item must be in the heap.141 */142 139 const PrioType& operator[](const Item& item) const { 143 140 return container[iimap[item]].prio; … … 145 142 146 143 147 ///Deletes the item with minimum priority w.r.t.Compare.148 149 /** 150 This method deletes the item with minimum priority w.r.t.151 Compare from the heap. 152 \pre The heap must be non-empty. 144 ///Deletes the item with minimum priority relative to \ref Compare. 145 146 /** 147 This method deletes the item with minimum priority relative to \ref 148 Compare from the heap. 149 \pre The heap must be non-empty. 153 150 */ 154 151 void pop(); … … 167 164 This method decreases the priority of \c item to \c value. 168 165 \pre \c item must be stored in the heap with priority at least \c 169 value w.r.t.Compare.166 value relative to \ref Compare. 170 167 */ 171 168 void decrease (Item item, PrioType const value); 172 173 169 174 170 ///Increases the priority of \c item to \c value. … … 177 173 This method sets the priority of \c item to \c value. Though 178 174 there is no precondition on the priority of \c item, this 179 method should be used only if there is a need to really \eincrease180 ( w.r.t.Compare) the priority of \c item, because this175 method should be used only if it is indeed necessary to increase 176 (relative to \ref Compare) the priority of \c item, because this 181 177 method is inefficient. 182 178 */ … … 187 183 188 184 189 /// Tells if \c item is in, was alreadyin, or has never been in the heap.185 ///Returns if \c item is in, has already been in, or has never been in the heap. 190 186 191 187 /**
Note: See TracChangeset
for help on using the changeset viewer.