Changeset 1270:806451fd084b in lemon0.x for src/lemon/bin_heap.h
 Timestamp:
 03/29/05 09:35:09 (19 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1698
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/bin_heap.h
r1191 r1270 21 21 ///\file 22 22 ///\brief Binary Heap implementation. 23 ///\todo It should be documented.24 23 25 24 #include <vector> … … 32 31 /// @{ 33 32 34 33 /// A Binary Heap implementation. 35 34 36 ///\todo Please document... 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>. 37 47 /// 38 48 ///\sa FibHeap … … 73 83 74 84 public: 75 ///\e 85 ///The constructor 86 87 /** 88 \c _iim should be given to the constructor, since it is used 89 internally to handle the cross references. 90 */ 76 91 explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {} 77 ///\e 92 93 ///The constructor 94 95 /** 96 \c _iim should be given to the constructor, since it is used 97 internally to handle the cross references. \c _comp is an 98 object for ordering of the priorities. 99 */ 78 100 BinHeap(ItemIntMap &_iim, const Compare &_comp) 79 101 : iim(_iim), comp(_comp) {} 80 102 81 103 82 ///\e 104 ///The number of items stored in the heap. 105 106 /** 107 Returns the number of items stored in the heap. 108 */ 83 109 int size() const { return data.size(); } 84 ///\e 110 111 ///Checks if the heap stores no items. 112 113 /** 114 Returns \c true if and only if the heap stores no items. 115 */ 85 116 bool empty() const { return data.empty(); } 86 117 … … 112 143 113 144 public: 114 ///\e 145 ///Adds \c p.first to the heap with priority \c p.second. 146 147 /** 148 Adds \c p.first to the heap with priority \c p.second. 149 \c p.first must not be stored in the heap. 150 */ 115 151 void push(const PairType &p) { 116 152 int n = data.size(); … … 118 154 bubble_up(n, p); 119 155 } 120 ///\e 156 157 ///Adds \c i to the heap with priority \c p. 158 159 /** 160 Adds \c i to the heap with priority \c p. 161 \pre \c i must not be stored in the heap. 162 */ 121 163 void push(const Item &i, const Prio &p) { push(PairType(i,p)); } 122 164 123 ///\e 165 ///Returns the item with minimum priority relative to \c Compare. 166 167 /** 168 This method returns the item with minimum priority relative to \c 169 Compare. 170 \pre The heap must be nonempty. 171 */ 124 172 Item top() const { 125 173 return data[0].first; 126 174 } 127 /// Returns the prio of the top element of the heap. 175 176 ///Returns the minimum priority relative to \c Compare. 177 178 /** 179 It returns the minimum priority relative to \c Compare. 180 \pre The heap must be nonempty. 181 */ 128 182 Prio prio() const { 129 183 return data[0].second; 130 184 } 131 185 132 ///\e 186 ///Deletes the item with minimum priority relative to \c Compare. 187 188 /** 189 This method deletes the item with minimum priority relative to \c 190 Compare from the heap. 191 \pre The heap must be nonempty. 192 */ 133 193 void pop() { 134 194 rmidx(0); 135 195 } 136 196 137 ///\e 197 ///Deletes \c i from the heap. 198 199 /** 200 This method deletes item \c i from the heap, if \c i was 201 already stored in the heap. 202 */ 138 203 void erase(const Item &i) { 139 204 rmidx(iim[i]); 140 205 } 141 206 142 ///\e 207 208 ///Returns the priority of \c i. 209 210 /** 211 This function returns the priority of item \c i. 212 \pre \c i must be in the heap. 213 */ 143 214 Prio operator[](const Item &i) const { 144 215 int idx = iim[i]; … … 146 217 } 147 218 148 ///\e 219 ///\c i gets to the heap with priority \c p independently if \c i was already there. 220 221 /** 222 This method calls \ref push(\c i, \c p) if \c i is not stored 223 in the heap and sets the priority of \c i to \c p otherwise. 224 */ 149 225 void set(const Item &i, const Prio &p) { 150 226 int idx = iim[i]; … … 160 236 } 161 237 162 ///\e 238 ///Decreases the priority of \c i to \c p. 239 240 /** 241 This method decreases the priority of item \c i to \c p. 242 \pre \c i must be stored in the heap with priority at least \c 243 p relative to \c Compare. 244 */ 163 245 void decrease(const Item &i, const Prio &p) { 164 246 int idx = iim[i]; 165 247 bubble_up(idx, PairType(i,p)); 166 248 } 167 ///\e 249 250 ///Increases the priority of \c i to \c p. 251 252 /** 253 This method sets the priority of item \c i to \c p. 254 \pre \c i must be stored in the heap with priority at most \c 255 p relative to \c Compare. 256 */ 168 257 void increase(const Item &i, const Prio &p) { 169 258 int idx = iim[i]; … … 171 260 } 172 261 173 ///\e 262 ///Returns if \c item is in, has already been in, or has never been in the heap. 263 264 /** 265 This method returns PRE_HEAP if \c item has never been in the 266 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 267 otherwise. In the latter case it is possible that \c item will 268 get back to the heap again. 269 */ 174 270 state_enum state(const Item &i) const { 175 271 int s = iim[i];
Note: See TracChangeset
for help on using the changeset viewer.