1[library Boost.Heap 2 [quickbook 1.4] 3 [authors [Blechmann, Tim]] 4 [copyright 2010-2011 Tim Blechmann] 5 [category algorithms] 6 [purpose 7 heap data structures 8 ] 9 [id heap] 10 [dirname heap] 11 [license 12 Distributed under the Boost Software License, Version 1.0. 13 (See accompanying file LICENSE_1_0.txt or copy at 14 [@http://www.boost.org/LICENSE_1_0.txt]) 15 ] 16] 17 18[c++] 19 20 21[/ Links ] 22 23[def _heap_ [^boost.heap]] 24 25[/ unspecified stuff ] 26[def __unspecified_int__ /unspecified-int-type/] 27[def __unspecified__ /unspecified/] 28[def __unspecified_bool__ /unspecified-bool-type/] 29 30[section Introduction & Motivation] 31 32_heap_ is an implementation of priority queues. Priority queues are queue data structures, that order their elements by 33a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality. 34To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and 35different performance characteristics. Especially, it deals with additional aspects: 36 37* *Mutability*: The priority of heap elements can be modified. 38* *Iterators*: Heaps provide iterators to iterate all elements. 39* *Mergable*: While all heaps can be merged, some can be merged efficiently. 40* *Stability*: Heaps can be configured to be stable sorted. 41* *Comparison*: Heaps can be compared for equivalence. 42 43[endsect] 44 45[section:concepts Concepts & Interface] 46 47[section:basic Basic Priority Queue Interface] 48 49Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to 50the data structure, accessing the top element (the element with the highest priority), and removing the top element. 51 52[note _heap_ implements priority queues as max-heaps to be consistent with the STL heap functions. This is in contrast to 53the typical textbook design, which uses min-heaps.] 54 55[h5 Synopsis] 56 57 template <typename T, class ...Options> 58 class priority_queue 59 { 60 // types 61 typedef T value_type; 62 typedef ``/unspecified/`` size_type; 63 typedef ``/unspecified/`` difference_type; 64 65 typedef ``/unspecified/`` allocator_type; 66 typedef ``/unspecified/`` value_compare; 67 68 typedef ``/unspecified/`` reference; 69 typedef ``/unspecified/`` const_reference; 70 typedef ``/unspecified/`` pointer; 71 typedef ``/unspecified/`` const_pointer; 72 73 // construct/copy/destruct 74 explicit priority_queue(value_compare const & = value_compare()); 75 priority_queue(priority_queue const &); 76 priority_queue& operator=(priority_queue const &); 77 priority_queue(priority_queue &&); // move semantics (C++11 only) 78 priority_queue& operator=(priority_queue &&); // move semantics (C++11 only) 79 80 // public member functions 81 ``/unspecified/`` push(const_reference); // push new element to heap 82 template<class... Args> void emplace(Args &&...); // push new element to heap, C++11 only 83 const_reference top() const; // return top element 84 void pop(); // remove top element 85 void clear(); // clear heap 86 size_type size() const; // number of elements 87 bool empty() const; // priority queue is empty 88 allocator_type get_allocator(void) const; // return allocator 89 size_type max_size(void) const; // maximal possible size 90 void reserve(size_type); // reserve space, only available if (has_reserve == true) 91 92 // heap equivalence 93 template<typename HeapType> bool operator==(HeapType const &) const; 94 template<typename HeapType> bool operator!=(HeapType const &) const; 95 96 // heap comparison 97 template<typename HeapType> bool operator<(HeapType const &) const; 98 template<typename HeapType> bool operator>(HeapType const &) const; 99 template<typename HeapType> bool operator>=(HeapType const &) const; 100 template<typename HeapType> bool operator<=(HeapType const &) const; 101 102 // public data members 103 static const bool constant_time_size; // size() has constant complexity 104 static const bool has_ordered_iterators; // priority queue has ``[link heap.concepts.iterators ordered iterators]`` 105 static const bool is_mergable; // priority queue is efficiently ``[link heap.concepts.merge mergable]`` 106 static const bool is_stable; // priority queue has a ``[link heap.concepts.stability stable heap order]`` 107 static const bool has_reserve; // priority queue has a reserve() member 108 }; 109 110[h5 Example] 111 112[import ../examples/interface.cpp] 113[basic_interface] 114 115[endsect] 116 117 118[section:iterators Priority Queue Iterators] 119 120[h5 Synopsis] 121 class iteratable_heap_interface 122 { 123 public: 124 // types 125 typedef ``/unspecified/`` iterator; 126 typedef ``/unspecified/`` const_iterator; 127 typedef ``/unspecified/`` ordered_iterator; 128 129 // public member functions 130 iterator begin(void) const; 131 iterator end(void) const; 132 ordered_iterator ordered_begin(void) const; 133 ordered_iterator ordered_end(void) const; 134 }; 135 136Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means 137they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about 138modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface]. 139 140Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate 141iterators, while all const member functions preserve the iterator validity. 142 143[note Some implementations require iterators, that contain a set of elements, that are *discovered*, but not *visited*. Therefore 144copying iterators can be inefficient and should be avoided.] 145 146[h5 Example] 147[iterator_interface] 148 149[section:ordered_iterators Ordered Iterators] 150 151Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements 152of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a 153heap in heap order has an amortized complexity of O(N*log(N)). 154 155[h5 Example] 156[ordered_iterator_interface] 157 158[endsect] 159 160[endsect] 161 162[section:comparing Comparing Priority Queues & Equivalence] 163 164The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two 165heaps element by element using =value_compare=. 166 167[note Depending on the heap type, this operation can be rather expensive, because both data structures need to be traversed in 168heap order. On heaps without ordered iterators, the heap needs to be copied internally. The typical complexity is O(n log(n)).] 169 170[endsect] 171 172 173[section:merge Merging Priority Queues] 174 175 176[h3 Mergable Priority Queues] 177 178[h5 Synopsis] 179 class mergable_heap_interface 180 { 181 public: 182 // public member functions 183 void merge(mergable_heap_interface &); 184 }; 185 186_heap_ has a concept of a Mergable Priority Queue. A mergable priority queue can efficiently be merged with a different instance 187of the same type. 188 189[h5 Example] 190[merge_interface] 191 192 193[h3 Heap Merge Algorithms] 194 195_heap_ provides a =heap_merge()= algorithm that is can be used to merge different kinds of heaps. Using this algorithm, all _heap_ 196data structures can be merged, although some cannot be merged efficiently. 197 198[h5 Example] 199[heap_merge_algorithm] 200 201[endsect] 202 203[section:mutability Mutability] 204 205Some priority queues of _heap_ are mutable, that means the priority of their elements can be changed. To achieve mutability, 206_heap_ introduces the concept of *handles*, which can be used to access the internal nodes of the priority queue in order to 207change its value and to restore the heap order. 208 209[h5 Synopsis] 210 class mutable_heap_interface 211 { 212 public: 213 typedef ``/unspecified/`` iterator; 214 struct handle_type 215 { 216 value_type & operator*() const; 217 }; 218 219 static handle_type s_iterator_to_handle(iterator const &); 220 221 // priority queue interface 222 handle_type push(T const & v); 223 224 // update element via assignment and fix heap 225 void update(handle_type const & handle, value_type const & v); 226 void increase(handle_type const & handle, value_type const & v); 227 void decrease(handle_type const & handle, value_type const & v); 228 229 // fix heap after element has been changed via the handle 230 void update(handle_type const & handle); 231 void increase(handle_type const & handle); 232 void decrease(handle_type const & handle); 233 }; 234 235[warning Incorrect use of =increase= or =decrease= may corrupt the priority queue data structure. If unsure use =update= can be 236used at the cost of efficiency.] 237 238[h5 Example] 239[mutable_interface] 240 241Note that handles can be stored inside the =value_type=: 242 243[mutable_interface_handle_in_value] 244 245[h3 The Fixup Interface] 246 247There are two different APIs to support mutability. The first family of functions provides update functionality by changing 248the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after 249an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue 250elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up 251immediately after the priority of the element has been changed. 252 253 254Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient 255than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right 256direction. 257 258[h5 Example] 259 260[mutable_fixup_interface] 261 262Iterators can be converted to handles using the static member function =s_handle_from_iterator=. However most implementations of 263=update= invalidate all iterators. The most notable exception is the [classref boost::heap::fibonacci_heap fibonacci heap], 264providing a lazy update function, that just invalidates the iterators, that are related to this handle. 265 266[warning After changing the priority via a handle, the heap needs to be fixed by calling one of the update functions. Otherwise the 267priority queue structure may be corrupted!] 268 269[endsect] 270 271[section:stability Stability] 272 273A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as 274they are inserted. The data structures provided by _heap_, can be configured to be stable at compile time using the 275[classref boost::heap::stable] policy. Two notions of stability are supported. If a heap is configured with *no stability*, 276the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by 277their insertion time. 278 279Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node. 280The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be 281configured to use a different type using the [classref boost::heap::stability_counter_type] template argument. 282 283[warning The stability counter is prone to integer overflows. If an overflow occurs during a =push()= call, the operation 284 will fail and an exception is thrown. Later =push()= call will succeed, but the stable heap order will be compromised. However an 285 integer overflow at 64bit is very unlikely: if an application would issue one =push()= operation per microsecond, the value will 286 overflow in more than 500000 years.] 287 288[endsect] 289 290 291[endsect] 292 293[section:data_structures Data Structures] 294_heap_ provides the following data structures: 295 296[variablelist 297 [[[classref boost::heap::priority_queue]] 298 [ 299 The [classref boost::heap::priority_queue priority_queue] class is a wrapper to the stl heap functions. It implements 300 a heap as container adaptor ontop of a =std::vector= and is immutable. 301 ] 302 ] 303 304 [[[classref boost::heap::d_ary_heap]] 305 [ 306 [@http://en.wikipedia.org/wiki/D-ary_heap D-ary heaps] are a generalization of binary heap with each non-leaf node 307 having N children. For a low arity, the height of the heap is larger, but the number of comparisons to find the largest 308 child node is bigger. D-ary heaps are implemented as container adaptors based on a =std::vector=. 309 310 The data structure can be configured as mutable. This is achieved by storing the values inside a std::list. 311 ] 312 ] 313 314 [[[classref boost::heap::binomial_heap]] 315 [ 316 [@http://en.wikipedia.org/wiki/Binomial_heap Binomial heaps] are node-base heaps, that are implemented as a set of 317 binomial trees of piecewise different order. The most important heap operations have a worst-case complexity of O(log n). 318 In contrast to d-ary heaps, binomial heaps can also be merged in O(log n). 319 ] 320 ] 321 322 [[[classref boost::heap::fibonacci_heap]] 323 [ 324 [@http://en.wikipedia.org/wiki/Fibonacci_heap Fibonacci heaps] are node-base heaps, that are implemented as a forest of 325 heap-ordered trees. They provide better amortized performance than binomial heaps. Except =pop()= and =erase()=, the most 326 important heap operations have constant amortized complexity. 327 ] 328 ] 329 330 [[[classref boost::heap::pairing_heap]] 331 [ 332 [@http://en.wikipedia.org/wiki/Pairing_heap Pairing heaps] are self-adjusting node-based heaps. Although design and 333 implementation are rather simple, the complexity analysis is yet unsolved. For details, consult: 334 335 Pettie, Seth (2005), "Towards a final analysis of pairing heaps", Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183 336 ] 337 ] 338 339 [[[classref boost::heap::skew_heap]] 340 [ 341 [@http://en.wikipedia.org/wiki/Skew_heap Skew heaps] are self-adjusting node-based heaps. Although there are no 342 constraints for the tree structure, all heap operations can be performed in O(log n). 343 ] 344 ] 345] 346 347[table Comparison of amortized complexity 348 [[] [[^top()]] [[^push()]] [[^pop()]] [[^update()]] [[^increase()]] [[^decrease()]] [[^erase()]] [[^merge_and_clear()]]] 349 [[[classref boost::heap::priority_queue]] [[^O(1)]] [O(log(N))] [O(log(N))] [n/a] [n/a] [n/a] [n/a] [O((N+M)*log(N+M))]] 350 [[[classref boost::heap::d_ary_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O((N+M)*log(N+M))]] 351 [[[classref boost::heap::binomial_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]] 352 [[[classref boost::heap::fibonacci_heap]] [[^O(1)]] [O(1)] [O(log(N))] [O(log(N)) 353 [footnote The fibonacci a [^update_lazy()] method, which has O(log(N)) amortized complexity as well, but does not try to consolidate the internal forest] 354 ] [O(1)] [O(log(N))] [O(log(N))] [O(1)]] 355 356 [[[classref boost::heap::pairing_heap]] [[^O(1)]] [O(2**2*log(log(N)))] [O(log(N))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))] [O(2**2*log(log(N)))]] 357 [[[classref boost::heap::skew_heap]] [[^O(1)]] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N))] [O(log(N+M))]] 358] 359 360 361 362[section Data Structure Configuration] 363 364The data structures can be configured with [@boost:/libs/parameter/doc/html/index.html Boost.Parameter]-style templates. 365 366[variablelist 367 [[[classref boost::heap::compare]] 368 [Predicate for defining the heap order, optional 369 (defaults to =boost::heap::compare<std::less<T> >=)] 370 ] 371 [[[classref boost::heap::allocator]] 372 [Allocator for internal memory management, optional 373 (defaults to =boost::heap::allocator<std::allocator<T> >=)] 374 ] 375 [[[classref boost::heap::stable]] 376 [Configures the heap to use a [link heap.concepts.stability stable heap order], optional (defaults to =boost::heap::stable<false>=). 377 ] 378 ] 379 [[[classref boost::heap::mutable_]] 380 [Configures the heap to be mutable. [classref boost::heap::d_ary_heap] and [classref boost::heap::skew_heap] have to be configured 381 with this policy to enable the [link heap.concepts.mutability mutability interface]. 382 ] 383 ] 384 [[[classref boost::heap::stability_counter_type]] 385 [Configures the integer type used for the stability counter, optional (defaults to =boost::heap::stability_counter_type<boost::uintmax_t>=). 386 For more details, consult the [link heap.concepts.stability Stability] section. 387 ] 388 ] 389 [[[classref boost::heap::constant_time_size]] 390 [Specifies, whether =size()= should have linear or constant complexity. This argument is only available for node-based 391 heap data structures and if available, it is optional (defaults to =boost::heap::constant_time_size<true>=)] 392 ] 393 394 [[[classref boost::heap::arity]] 395 [Specifies the arity of a d-ary heap. For details, please consult the class reference of [classref boost::heap::d_ary_heap]] 396 ] 397 398 [[[classref boost::heap::store_parent_pointer]] 399 [Store the parent pointer in the heap nodes. This policy is only available in the [classref boost::heap::skew_heap]. 400 ] 401 ] 402] 403 404[endsect] 405 406[endsect] 407 408 409[xinclude autodoc.xml] 410 411 412[section Acknowledgements] 413 414[variablelist 415 [[Google Inc.] 416 [For sponsoring the development of this library during the Summer of Code 2010] 417 ] 418 [[Hartmut Kaiser] 419 [For mentoring the Summer of Code project] 420 ] 421] 422[endsect]