doc/html/heap/data_structures.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Data Structures</title>
   5 <link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
   8 <link rel="up" href="../heap.html" title="Chapter&#160;13.&#160;Boost.Heap">
   9 <link rel="prev" href="concepts.html" title="Concepts &amp; Interface">
  10 <link rel="next" href="reference.html" title="Reference">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
  15 <td align="center"><a href="../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="concepts.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../heap.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h2 class="title" style="clear: both">
  27 <a name="heap.data_structures"></a><a class="link" href="data_structures.html" title="Data Structures">Data Structures</a>
  28 </h2></div></div></div>
  29 <div class="toc"><dl class="toc"><dt><span class="section"><a href="data_structures.html#heap.data_structures.data_structure_configuration">Data
  30       Structure Configuration</a></span></dt></dl></div>
  31 <p>
  32       <code class="literal">boost.heap</code> provides the following data structures:
  33     </p>
  34 <div class="variablelist">
  35 <p class="title"><b></b></p>
  36 <dl class="variablelist">
  37 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/priority_queue.html" title="Class template priority_queue">boost::heap::priority_queue</a></code></span></dt>
  38 <dd><p>
  39             The <code class="computeroutput"><a class="link" href="../boost/heap/priority_queue.html" title="Class template priority_queue">priority_queue</a></code>
  40             class is a wrapper to the stl heap functions. It implements a heap as
  41             container adaptor ontop of a <code class="literal">std::vector</code> and is immutable.
  42           </p></dd>
  43 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/d_ary_heap.html" title="Class template d_ary_heap">boost::heap::d_ary_heap</a></code></span></dt>
  44 <dd>
  45 <p>
  46             <a href="http://en.wikipedia.org/wiki/D-ary_heap" target="_top">D-ary heaps</a>
  47             are a generalization of binary heap with each non-leaf node having N
  48             children. For a low arity, the height of the heap is larger, but the
  49             number of comparisons to find the largest child node is bigger. D-ary
  50             heaps are implemented as container adaptors based on a <code class="literal">std::vector</code>.
  51           </p>
  52 <p>
  53             The data structure can be configured as mutable. This is achieved by
  54             storing the values inside a std::list.
  55           </p>
  56 </dd>
  57 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/binomial_heap.html" title="Class template binomial_heap">boost::heap::binomial_heap</a></code></span></dt>
  58 <dd><p>
  59             <a href="http://en.wikipedia.org/wiki/Binomial_heap" target="_top">Binomial heaps</a>
  60             are node-base heaps, that are implemented as a set of binomial trees
  61             of piecewise different order. The most important heap operations have
  62             a worst-case complexity of O(log n). In contrast to d-ary heaps, binomial
  63             heaps can also be merged in O(log n).
  64           </p></dd>
  65 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/fibonacci_heap.html" title="Class template fibonacci_heap">boost::heap::fibonacci_heap</a></code></span></dt>
  66 <dd><p>
  67             <a href="http://en.wikipedia.org/wiki/Fibonacci_heap" target="_top">Fibonacci heaps</a>
  68             are node-base heaps, that are implemented as a forest of heap-ordered
  69             trees. They provide better amortized performance than binomial heaps.
  70             Except <code class="literal">pop()</code> and <code class="literal">erase()</code>, the most
  71             important heap operations have constant amortized complexity.
  72           </p></dd>
  73 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/pairing_heap.html" title="Class template pairing_heap">boost::heap::pairing_heap</a></code></span></dt>
  74 <dd>
  75 <p>
  76             <a href="http://en.wikipedia.org/wiki/Pairing_heap" target="_top">Pairing heaps</a>
  77             are self-adjusting node-based heaps. Although design and implementation
  78             are rather simple, the complexity analysis is yet unsolved. For details,
  79             consult:
  80           </p>
  81 <p>
  82             Pettie, Seth (2005), "Towards a final analysis of pairing heaps",
  83             Proc. 46th Annual IEEE Symposium on Foundations of Computer Science,
  84             pp. 174&#8211;183
  85           </p>
  86 </dd>
  87 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/skew_heap.html" title="Class template skew_heap">boost::heap::skew_heap</a></code></span></dt>
  88 <dd><p>
  89             <a href="http://en.wikipedia.org/wiki/Skew_heap" target="_top">Skew heaps</a>
  90             are self-adjusting node-based heaps. Although there are no constraints
  91             for the tree structure, all heap operations can be performed in O(log
  92             n).
  93           </p></dd>
  94 </dl>
  95 </div>
  96 <div class="table">
  97 <a name="heap.data_structures.t0"></a><p class="title"><b>Table&#160;13.1.&#160;Comparison of amortized complexity</b></p>
  98 <div class="table-contents"><table class="table" summary="Comparison of amortized complexity">
  99 <colgroup>
 100 <col>
 101 <col>
 102 <col>
 103 <col>
 104 <col>
 105 <col>
 106 <col>
 107 <col>
 108 <col>
 109 </colgroup>
 110 <thead><tr>
 111 <th>
 112             </th>
 113 <th>
 114               <p>
 115                 <code class="literal">top()</code>
 116               </p>
 117             </th>
 118 <th>
 119               <p>
 120                 <code class="literal">push()</code>
 121               </p>
 122             </th>
 123 <th>
 124               <p>
 125                 <code class="literal">pop()</code>
 126               </p>
 127             </th>
 128 <th>
 129               <p>
 130                 <code class="literal">update()</code>
 131               </p>
 132             </th>
 133 <th>
 134               <p>
 135                 <code class="literal">increase()</code>
 136               </p>
 137             </th>
 138 <th>
 139               <p>
 140                 <code class="literal">decrease()</code>
 141               </p>
 142             </th>
 143 <th>
 144               <p>
 145                 <code class="literal">erase()</code>
 146               </p>
 147             </th>
 148 <th>
 149               <p>
 150                 <code class="literal">merge_and_clear()</code>
 151               </p>
 152             </th>
 153 </tr></thead>
 154 <tbody>
 155 <tr>
 156 <td>
 157               <p>
 158                 <code class="computeroutput"><a class="link" href="../boost/heap/priority_queue.html" title="Class template priority_queue">boost::heap::priority_queue</a></code>
 159               </p>
 160             </td>
 161 <td>
 162               <p>
 163                 <code class="literal">O(1)</code>
 164               </p>
 165             </td>
 166 <td>
 167               <p>
 168                 O(log(N))
 169               </p>
 170             </td>
 171 <td>
 172               <p>
 173                 O(log(N))
 174               </p>
 175             </td>
 176 <td>
 177               <p>
 178                 n/a
 179               </p>
 180             </td>
 181 <td>
 182               <p>
 183                 n/a
 184               </p>
 185             </td>
 186 <td>
 187               <p>
 188                 n/a
 189               </p>
 190             </td>
 191 <td>
 192               <p>
 193                 n/a
 194               </p>
 195             </td>
 196 <td>
 197               <p>
 198                 O((N+M)*log(N+M))
 199               </p>
 200             </td>
 201 </tr>
 202 <tr>
 203 <td>
 204               <p>
 205                 <code class="computeroutput"><a class="link" href="../boost/heap/d_ary_heap.html" title="Class template d_ary_heap">boost::heap::d_ary_heap</a></code>
 206               </p>
 207             </td>
 208 <td>
 209               <p>
 210                 <code class="literal">O(1)</code>
 211               </p>
 212             </td>
 213 <td>
 214               <p>
 215                 O(log(N))
 216               </p>
 217             </td>
 218 <td>
 219               <p>
 220                 O(log(N))
 221               </p>
 222             </td>
 223 <td>
 224               <p>
 225                 O(log(N))
 226               </p>
 227             </td>
 228 <td>
 229               <p>
 230                 O(log(N))
 231               </p>
 232             </td>
 233 <td>
 234               <p>
 235                 O(log(N))
 236               </p>
 237             </td>
 238 <td>
 239               <p>
 240                 O(log(N))
 241               </p>
 242             </td>
 243 <td>
 244               <p>
 245                 O((N+M)*log(N+M))
 246               </p>
 247             </td>
 248 </tr>
 249 <tr>
 250 <td>
 251               <p>
 252                 <code class="computeroutput"><a class="link" href="../boost/heap/binomial_heap.html" title="Class template binomial_heap">boost::heap::binomial_heap</a></code>
 253               </p>
 254             </td>
 255 <td>
 256               <p>
 257                 <code class="literal">O(1)</code>
 258               </p>
 259             </td>
 260 <td>
 261               <p>
 262                 O(log(N))
 263               </p>
 264             </td>
 265 <td>
 266               <p>
 267                 O(log(N))
 268               </p>
 269             </td>
 270 <td>
 271               <p>
 272                 O(log(N))
 273               </p>
 274             </td>
 275 <td>
 276               <p>
 277                 O(log(N))
 278               </p>
 279             </td>
 280 <td>
 281               <p>
 282                 O(log(N))
 283               </p>
 284             </td>
 285 <td>
 286               <p>
 287                 O(log(N))
 288               </p>
 289             </td>
 290 <td>
 291               <p>
 292                 O(log(N+M))
 293               </p>
 294             </td>
 295 </tr>
 296 <tr>
 297 <td>
 298               <p>
 299                 <code class="computeroutput"><a class="link" href="../boost/heap/fibonacci_heap.html" title="Class template fibonacci_heap">boost::heap::fibonacci_heap</a></code>
 300               </p>
 301             </td>
 302 <td>
 303               <p>
 304                 <code class="literal">O(1)</code>
 305               </p>
 306             </td>
 307 <td>
 308               <p>
 309                 O(1)
 310               </p>
 311             </td>
 312 <td>
 313               <p>
 314                 O(log(N))
 315               </p>
 316             </td>
 317 <td>
 318               <p>
 319                 O(log(N)) <a href="#ftn.heap.data_structures.f0" class="footnote" name="heap.data_structures.f0"><sup class="footnote">[a]</sup></a>
 320               </p>
 321             </td>
 322 <td>
 323               <p>
 324                 O(1)
 325               </p>
 326             </td>
 327 <td>
 328               <p>
 329                 O(log(N))
 330               </p>
 331             </td>
 332 <td>
 333               <p>
 334                 O(log(N))
 335               </p>
 336             </td>
 337 <td>
 338               <p>
 339                 O(1)
 340               </p>
 341             </td>
 342 </tr>
 343 <tr>
 344 <td>
 345               <p>
 346                 <code class="computeroutput"><a class="link" href="../boost/heap/pairing_heap.html" title="Class template pairing_heap">boost::heap::pairing_heap</a></code>
 347               </p>
 348             </td>
 349 <td>
 350               <p>
 351                 <code class="literal">O(1)</code>
 352               </p>
 353             </td>
 354 <td>
 355               <p>
 356                 O(2**2*log(log(N)))
 357               </p>
 358             </td>
 359 <td>
 360               <p>
 361                 O(log(N))
 362               </p>
 363             </td>
 364 <td>
 365               <p>
 366                 O(2**2*log(log(N)))
 367               </p>
 368             </td>
 369 <td>
 370               <p>
 371                 O(2**2*log(log(N)))
 372               </p>
 373             </td>
 374 <td>
 375               <p>
 376                 O(2**2*log(log(N)))
 377               </p>
 378             </td>
 379 <td>
 380               <p>
 381                 O(2**2*log(log(N)))
 382               </p>
 383             </td>
 384 <td>
 385               <p>
 386                 O(2**2*log(log(N)))
 387               </p>
 388             </td>
 389 </tr>
 390 <tr>
 391 <td>
 392               <p>
 393                 <code class="computeroutput"><a class="link" href="../boost/heap/skew_heap.html" title="Class template skew_heap">boost::heap::skew_heap</a></code>
 394               </p>
 395             </td>
 396 <td>
 397               <p>
 398                 <code class="literal">O(1)</code>
 399               </p>
 400             </td>
 401 <td>
 402               <p>
 403                 O(log(N))
 404               </p>
 405             </td>
 406 <td>
 407               <p>
 408                 O(log(N))
 409               </p>
 410             </td>
 411 <td>
 412               <p>
 413                 O(log(N))
 414               </p>
 415             </td>
 416 <td>
 417               <p>
 418                 O(log(N))
 419               </p>
 420             </td>
 421 <td>
 422               <p>
 423                 O(log(N))
 424               </p>
 425             </td>
 426 <td>
 427               <p>
 428                 O(log(N))
 429               </p>
 430             </td>
 431 <td>
 432               <p>
 433                 O(log(N+M))
 434               </p>
 435             </td>
 436 </tr>
 437 </tbody>
 438 <tbody class="footnotes"><tr><td colspan="9"><div id="ftn.heap.data_structures.f0" class="footnote"><p><a href="#heap.data_structures.f0" class="para"><sup class="para">[a] </sup></a>
 439                   The fibonacci a <code class="literal">update_lazy()</code> method, which
 440                   has O(log(N)) amortized complexity as well, but does not try to
 441                   consolidate the internal forest
 442                 </p></div></td></tr></tbody>
 443 </table></div>
 444 </div>
 445 <br class="table-break"><div class="section">
 446 <div class="titlepage"><div><div><h3 class="title">
 447 <a name="heap.data_structures.data_structure_configuration"></a><a class="link" href="data_structures.html#heap.data_structures.data_structure_configuration" title="Data Structure Configuration">Data
 448       Structure Configuration</a>
 449 </h3></div></div></div>
 450 <p>
 451         The data structures can be configured with <a href="../../../libs/parameter/doc/html/index.html" target="_top">Boost.Parameter</a>-style
 452         templates.
 453       </p>
 454 <div class="variablelist">
 455 <p class="title"><b></b></p>
 456 <dl class="variablelist">
 457 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/compare.html" title="Struct template compare">boost::heap::compare</a></code></span></dt>
 458 <dd><p>
 459               Predicate for defining the heap order, optional (defaults to <code class="literal">boost::heap::compare&lt;std::less&lt;T&gt;
 460               &gt;</code>)
 461             </p></dd>
 462 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/allocator.html" title="Struct template allocator">boost::heap::allocator</a></code></span></dt>
 463 <dd><p>
 464               Allocator for internal memory management, optional (defaults to <code class="literal">boost::heap::allocator&lt;std::allocator&lt;T&gt;
 465               &gt;</code>)
 466             </p></dd>
 467 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/stable.html" title="Struct template stable">boost::heap::stable</a></code></span></dt>
 468 <dd><p>
 469               Configures the heap to use a <a class="link" href="concepts.html#heap.concepts.stability" title="Stability">stable
 470               heap order</a>, optional (defaults to <code class="literal">boost::heap::stable&lt;false&gt;</code>).
 471             </p></dd>
 472 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/mutable_.html" title="Struct template mutable_">boost::heap::mutable_</a></code></span></dt>
 473 <dd><p>
 474               Configures the heap to be mutable. <code class="computeroutput"><a class="link" href="../boost/heap/d_ary_heap.html" title="Class template d_ary_heap">boost::heap::d_ary_heap</a></code>
 475               and <code class="computeroutput"><a class="link" href="../boost/heap/skew_heap.html" title="Class template skew_heap">boost::heap::skew_heap</a></code>
 476               have to be configured with this policy to enable the <a class="link" href="concepts.html#heap.concepts.mutability" title="Mutability">mutability
 477               interface</a>.
 478             </p></dd>
 479 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/stability_counter_type.html" title="Struct template stability_counter_type">boost::heap::stability_counter_type</a></code></span></dt>
 480 <dd><p>
 481               Configures the integer type used for the stability counter, optional
 482               (defaults to <code class="literal">boost::heap::stability_counter_type&lt;boost::uintmax_t&gt;</code>).
 483               For more details, consult the <a class="link" href="concepts.html#heap.concepts.stability" title="Stability">Stability</a>
 484               section.
 485             </p></dd>
 486 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/constant_time_size.html" title="Struct template constant_time_size">boost::heap::constant_time_size</a></code></span></dt>
 487 <dd><p>
 488               Specifies, whether <code class="literal">size()</code> should have linear or
 489               constant complexity. This argument is only available for node-based
 490               heap data structures and if available, it is optional (defaults to
 491               <code class="literal">boost::heap::constant_time_size&lt;true&gt;</code>)
 492             </p></dd>
 493 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/arity.html" title="Struct template arity">boost::heap::arity</a></code></span></dt>
 494 <dd><p>
 495               Specifies the arity of a d-ary heap. For details, please consult the
 496               class reference of <code class="computeroutput"><a class="link" href="../boost/heap/d_ary_heap.html" title="Class template d_ary_heap">boost::heap::d_ary_heap</a></code>
 497             </p></dd>
 498 <dt><span class="term"><code class="computeroutput"><a class="link" href="../boost/heap/store_parent_pointer.html" title="Struct template store_parent_pointer">boost::heap::store_parent_pointer</a></code></span></dt>
 499 <dd><p>
 500               Store the parent pointer in the heap nodes. This policy is only available
 501               in the <code class="computeroutput"><a class="link" href="../boost/heap/skew_heap.html" title="Class template skew_heap">boost::heap::skew_heap</a></code>.
 502             </p></dd>
 503 </dl>
 504 </div>
 505 </div>
 506 </div>
 507 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 508 <td align="left"></td>
 509 <td align="right"><div class="copyright-footer">Copyright &#169; 2010, 2011 Tim Blechmann<p>
 510         Distributed under the Boost Software License, Version 1.0. (See accompanying
 511         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 512       </p>
 513 </div></td>
 514 </tr></table>
 515 <hr>
 516 <div class="spirit-nav">
 517 <a accesskey="p" href="concepts.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../heap.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="reference.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
 518 </div>
 519 </body>
 520 </html>