ceph/src/boost/libs/heap/doc/heap.qbk

   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
  33 a priority. The STL provides a single template class =std::priority_queue=, which only provides a limited functionality.
  34 To overcome these limitations, _heap_ implements [link heap.data_structures data structures] with more functionality and
  35 different 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
  49 Priority queues are queues of objects, that are ordered by their priority. They support the operations of adding nodes to
  50 the 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
  53 the 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
 136 Priority queues provide iterators, that can be used to traverse their elements. All heap iterators are const_iterators, that means
 137 they cannot be used to modify the values, because changing the value of a heap node may corrupt the heap order. Details about
 138 modifying heap nodes are described in the section about the [link heap.concepts.mutability mutability interface].
 139
 140 Iterators do not visit heap elements in any specific order. Unless otherwise noted, all non-const heap member functions invalidate
 141 iterators, 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
 144 copying iterators can be inefficient and should be avoided.]
 145
 146 [h5 Example]
 147 [iterator_interface]
 148
 149 [section:ordered_iterators Ordered Iterators]
 150
 151 Except for [classref boost::heap::priority_queue] all _heap_ data structures support ordered iterators, which visit all elements
 152 of the heap in heap-order. The implementation of these [^ordered_iterator]s requires some internal bookkeeping, so iterating the a
 153 heap 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
 164 The data structures of _heap_ can be compared with standard comparison operators. The comparison is performed by comparing two
 165 heaps 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
 168 heap 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
 187 of 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_
 196 data 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
 205 Some 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
 207 change 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
 236 used at the cost of efficiency.]
 237
 238 [h5 Example]
 239 [mutable_interface]
 240
 241 Note that handles can be stored inside the =value_type=:
 242
 243 [mutable_interface_handle_in_value]
 244
 245 [h3 The Fixup Interface]
 246
 247 There are two different APIs to support mutability. The first family of functions provides update functionality by changing
 248 the current element by assigning a new value. The second family of functions can be used to fix the heap data structure after
 249 an element has been changed directly via a handle. While this provides the user with a means to modify the priority of queue
 250 elements without the need to change their non-priority part, this needs to be handled with care. The heap needs to be fixed up
 251 immediately after the priority of the element has been changed.
 252
 253
 254 Beside an =update= function, two additional functions =increase= and =decrease= are provided, that are generally more efficient
 255 than the generic =update= function. However the user has do ensure, that the priority of an element is changed to the right
 256 direction.
 257
 258 [h5 Example]
 259
 260 [mutable_fixup_interface]
 261
 262 Iterators can be coverted 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],
 264 providing 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
 267 priority queue structure may be corrupted!]
 268
 269 [endsect]
 270
 271 [section:stability Stability]
 272
 273 A priority queue is `stable', if elements with the same priority are popped from the heap, in the same order as
 274 they 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*,
 276 the order of nodes of the same priority is undefined, if it is configured as *stable*, nodes of the same priority are ordered by
 277 their insertion time.
 278
 279 Stability is achieved by associating an integer version count with each value in order to distinguish values with the same node.
 280 The type of this version count defaults to =boost::uintmax_t=, which is at least 64bit on most systems. However it can be
 281 configured 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
 364 The 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]