| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" |
| "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> |
| <head> |
| <meta name="generator" content= |
| "HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" /> |
| |
| <title>Priority-Queues</title> |
| <meta http-equiv="Content-Type" content= |
| "text/html; charset=us-ascii" /> |
| </head> |
| |
| <body> |
| <div id="page"> |
| <h1>Priority-Queue Design</h1> |
| |
| <h2><a name="overview" id="overview">Overview</a></h2> |
| |
| <p>The priority-queue container has the following |
| declaration:</p> |
| <pre> |
| <b>template</b>< |
| <b>typename</b> Value_Type, |
| <b>typename</b> Cmp_Fn = std::less<Value_Type>, |
| <b>typename</b> Tag = <a href="pairing_heap_tag.html">pairing_heap_tag</a>, |
| <b>typename</b> Allocator = std::allocator<<b>char</b>> > |
| <b>class</b> <a href="priority_queue.html">priority_queue</a>; |
| </pre> |
| |
| <p>The parameters have the following meaning:</p> |
| |
| <ol> |
| <li><tt>Value_Type</tt> is the value type.</li> |
| |
| <li><tt>Cmp_Fn</tt> is a value comparison functor</li> |
| |
| <li><tt>Tag</tt> specifies which underlying data structure |
| to use.</li> |
| |
| <li><tt>Allocator</tt> is an allocator |
| type.</li> |
| </ol> |
| |
| <p>The <tt>Tag</tt> parameter specifies which underlying |
| data structure to use. Instantiating it by <a href= |
| "pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>, |
| <a href= |
| "binary_heap_tag.html"><tt>binary_heap_tag</tt></a>, |
| <a href= |
| "binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>, |
| <a href= |
| "rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>, |
| or <a href= |
| "thin_heap_tag.html"><tt>thin_heap_tag</tt></a>, |
| specifies, respectively, an underlying pairing heap [<a href= |
| "references.html#fredman86pairing">fredman86pairing</a>], |
| binary heap [<a href="references.html#clrs2001">clrs2001</a>], |
| binomial heap [<a href= |
| "references.html#clrs2001">clrs2001</a>], a binomial heap with |
| a redundant binary counter [<a href= |
| "references.html#maverik_lowerbounds">maverik_lowerbounds</a>], |
| or a thin heap [<a href= |
| "references.html#kt99fat_heaps">kt99fat_heas</a>]. These are |
| explained further in <a href="#pq_imp">Implementations</a>.</p> |
| |
| <p>As mentioned in <a href= |
| "tutorial.html#pq">Tutorial::Priority Queues</a>, |
| <a href= |
| "priority_queue.html"><tt>pb_ds::priority_queue</tt></a> |
| shares most of the same interface with <tt>std::priority_queue</tt>. |
| <i>E.g.</i> if <tt>q</tt> is a priority queue of type |
| <tt>Q</tt>, then <tt>q.top()</tt> will return the "largest" |
| value in the container (according to <tt><b>typename</b> |
| Q::cmp_fn</tt>). <a href= |
| "priority_queue.html"><tt>pb_ds::priority_queue</tt></a> |
| has a larger (and very slightly different) interface than |
| <tt>std::priority_queue</tt>, however, since typically |
| <tt>push</tt> and <tt>pop</tt> are deemed insufficient for |
| manipulating priority-queues. </p> |
| |
| <p>Different settings require different priority-queue |
| implementations which are described in <a href= |
| "#pq_imp">Implementations</a>; <a href="#pq_traits">Traits</a> |
| discusses ways to differentiate between the different traits of |
| different implementations.</p> |
| |
| <h2><a name="pq_it" id="pq_it">Iterators</a></h2> |
| |
| <p>There are many different underlying-data structures for |
| implementing priority queues. Unfortunately, most such |
| structures are oriented towards making <tt>push</tt> and |
| <tt>top</tt> efficient, and consequently don't allow efficient |
| access of other elements: for instance, they cannot support an efficient |
| <tt>find</tt> method. In the use case where it |
| is important to both access and "do something with" an |
| arbitrary value, one would be out of luck. For example, many graph algorithms require |
| modifying a value (typically increasing it in the sense of the |
| priority queue's comparison functor).</p> |
| |
| <p>In order to access and manipulate an arbitrary value in a |
| priority queue, one needs to reference the internals of the |
| priority queue from some form of an associative container - |
| this is unavoidable. Of course, in order to maintain the |
| encapsulation of the priority queue, this needs to be done in a |
| way that minimizes exposure to implementation internals.</p> |
| |
| <p>In <tt>pb_ds</tt> the priority queue's <tt>insert</tt> |
| method returns an iterator, which if valid can be used for subsequent <tt>modify</tt> and |
| <tt>erase</tt> operations. This both preserves the priority |
| queue's encapsulation, and allows accessing arbitrary values (since the |
| returned iterators from the <tt>push</tt> operation can be |
| stored in some form of associative container).</p> |
| |
| <p>Priority queues' iterators present a problem regarding their |
| invalidation guarantees. One assumes that calling |
| <tt><b>operator</b>++</tt> on an iterator will associate it |
| with the "next" value. Priority-queues are |
| self-organizing: each operation changes what the "next" value |
| means. Consequently, it does not make sense that <tt>push</tt> |
| will return an iterator that can be incremented - this can have |
| no possible use. Also, as in the case of hash-based containers, |
| it is awkward to define if a subsequent <tt>push</tt> operation |
| invalidates a prior returned iterator: it invalidates it in the |
| sense that its "next" value is not related to what it |
| previously considered to be its "next" value. However, it might not |
| invalidate it, in the sense that it can be |
| de-referenced and used for <tt>modify</tt> and <tt>erase</tt> |
| operations.</p> |
| |
| <p>Similarly to the case of the other unordered associative |
| containers, <tt>pb_ds</tt> uses a distinction between |
| point-type and range type iterators. A priority queue's <tt>iterator</tt> can always be |
| converted to a <tt>point_iterator</tt>, and a |
| <tt>const_iterator</tt> can always be converted to a |
| <tt>const_point_iterator</tt>.</p> |
| |
| <p>The following snippet demonstrates manipulating an arbitrary |
| value:</p> |
| <pre> |
| <i>// A priority queue of integers.</i> |
| <a href= |
| "priority_queue.html">priority_queue</a><<b>int</b>> p; |
| |
| <i>// Insert some values into the priority queue.</i> |
| <a href= |
| "priority_queue.html">priority_queue</a><<b>int</b>>::point_iterator it = p.push(0); |
| |
| p.push(1); |
| p.push(2); |
| |
| <i>// Now modify a value.</i> |
| p.modify(it, 3); |
| |
| assert(p.top() == 3); |
| </pre> |
| |
| <p>(<a href="pq_examples.html#xref">Priority Queue |
| Examples::Cross-Referencing</a> shows a more detailed |
| example.)</p> |
| |
| <p>It should be noted that an alternative design could embed an |
| associative container in a priority queue. Could, but most probably should not. To begin with, it should be noted that one |
| could always encapsulate a priority queue and an associative |
| container mapping values to priority queue iterators with no |
| performance loss. One cannot, however, "un-encapsulate" a |
| priority queue embedding an associative container, which might |
| lead to performance loss. Assume, that one needs to |
| associate each value with some data unrelated to priority |
| queues. Then using <tt>pb_ds</tt>'s design, one could use an |
| associative container mapping each value to a pair consisting |
| of this data and a priority queue's iterator. Using the |
| embedded method would need to use two associative |
| containers. Similar problems might arise in cases where a value |
| can reside simultaneously in many priority queues.</p> |
| |
| <h2><a name="pq_imp" id="pq_imp">Implementations</a></h2> |
| |
| <p>There are three main implementations of priority queues: the |
| first employs a binary heap, typically one which uses a |
| sequence; the second uses a tree (or forest of trees), which is |
| typically less structured than an associative container's tree; |
| the third simply uses an associative container. These are |
| shown, respectively, in Figures <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> A1 and A2, Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> B, and Figures <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> C.</p> |
| |
| <h6 class="c1"><a name="pq_different_underlying_dss" id= |
| "pq_different_underlying_dss"><img src= |
| "pq_different_underlying_dss.png" alt="no image" /></a></h6> |
| |
| <h6 class="c1">Underlying Priority-Queue Data-Structures.</h6> |
| |
| <p>Roughly speaking, any value that is both pushed and popped |
| from a priority queue must incur a logarithmic expense (in the |
| amortized sense). Any priority queue implementation that would |
| avoid this, would violate known bounds on comparison-based |
| sorting (see, <i>e.g.</i>, [<a href= |
| "references.html#clrs2001">clrs2001</a>] and <a href= |
| "references.html#brodal96priority">brodal96priority</a>]).</p> |
| |
| <p>Most implementations do |
| not differ in the asymptotic amortized complexity of |
| <tt>push</tt> and <tt>pop</tt> operations, but they differ in |
| the constants involved, in the complexity of other operations |
| (<i>e.g.</i>, <tt>modify</tt>), and in the worst-case |
| complexity of single operations. In general, the more |
| "structured" an implementation (<i>i.e.</i>, the more internal |
| invariants it possesses) - the higher its amortized complexity |
| of <tt>push</tt> and <tt>pop</tt> operations.</p> |
| |
| <p><tt>pb_ds</tt> implements different algorithms using a |
| single class: <a href="priority_queue.html">priority_queue</a>. |
| Instantiating the <tt>Tag</tt> template parameter, "selects" |
| the implementation:</p> |
| |
| <ol> |
| <li>Instantiating <tt>Tag = <a href= |
| "binary_heap_tag.html">binary_heap_tag</a></tt> creates |
| a binary heap of the form in Figures <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> A1 or A2. The former is internally |
| selected by <a href="priority_queue.html">priority_queue</a> |
| if <tt>Value_Type</tt> is instantiated by a primitive type |
| (<i>e.g.</i>, an <tt><b>int</b></tt>); the latter is |
| internally selected for all other types (<i>e.g.</i>, |
| <tt>std::string</tt>). This implementations is relatively |
| unstructured, and so has good <tt>push</tt> and <tt>pop</tt> |
| performance; it is the "best-in-kind" for primitive |
| types, <i>e.g.</i>, <tt><b>int</b></tt>s. Conversely, it has |
| high worst-case performance, and can support only linear-time |
| <tt>modify</tt> and <tt>erase</tt> operations; this is |
| explained further in <a href="#pq_traits">Traits</a>.</li> |
| |
| <li>Instantiating <tt>Tag = <a href= |
| "pairing_heap_tag.html">pairing_heap_tag</a></tt> |
| creates a pairing heap of the form in Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> B. This implementations too is relatively |
| unstructured, and so has good <tt>push</tt> and <tt>pop</tt> |
| performance; it is the "best-in-kind" for non-primitive |
| types, <i>e.g.</i>, <tt>std:string</tt>s. It also has very |
| good worst-case <tt>push</tt> and <tt>join</tt> performance |
| (<i>O(1)</i>), but has high worst-case <tt>pop</tt> |
| complexity.</li> |
| |
| <li>Instantiating <tt>Tag = <a href= |
| "binomial_heap_tag.html">binomial_heap_tag</a></tt> |
| creates a binomial heap of the form in Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> B. This implementations is more |
| structured than a pairing heap, and so has worse |
| <tt>push</tt> and <tt>pop</tt> performance. Conversely, it |
| has sub-linear worst-case bounds for <tt>pop</tt>, |
| <i>e.g.</i>, and so it might be preferred in cases where |
| responsiveness is important.</li> |
| |
| <li>Instantiating <tt>Tag = <a href= |
| "rc_binomial_heap_tag.html">rc_binomial_heap_tag</a></tt> |
| creates a binomial heap of the form in Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> B, accompanied by a redundant counter |
| which governs the trees. This implementations is therefore |
| more structured than a binomial heap, and so has worse |
| <tt>push</tt> and <tt>pop</tt> performance. Conversely, it |
| guarantees <i>O(1)</i> <tt>push</tt> complexity, and so it |
| might be preferred in cases where the responsiveness of a |
| binomial heap is insufficient.</li> |
| |
| <li>Instantiating <tt>Tag = <a href= |
| "thin_heap_tag.html">thin_heap_tag</a></tt> creates a |
| thin heap of the form in Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> B. This implementations too is more |
| structured than a pairing heap, and so has worse |
| <tt>push</tt> and <tt>pop</tt> performance. Conversely, it |
| has better worst-case and identical amortized complexities |
| than a Fibonacci heap, and so might be more appropriate for |
| some graph algorithms.</li> |
| </ol> |
| |
| <p><a href="pq_performance_tests.html">Priority-Queue |
| Performance Tests</a> shows some results for the above, and |
| discusses these points further.</p> |
| |
| <p>Of course, one can use any order-preserving associative |
| container as a priority queue, as in Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> C, possibly by creating an adapter class |
| over the associative container (much as |
| <tt>std::priority_queue</tt> can adapt <tt>std::vector</tt>). |
| This has the advantage that no cross-referencing is necessary |
| at all; the priority queue itself is an associative container. |
| Most associative containers are too structured to compete with |
| priority queues in terms of <tt>push</tt> and <tt>pop</tt> |
| performance.</p> |
| |
| <h2><a name="pq_traits" id="pq_traits">Traits</a></h2> |
| |
| <p>It would be nice if all priority queues could |
| share exactly the same behavior regardless of implementation. Sadly, this is not possible. Just one for instance is in join operations: joining |
| two binary heaps might throw an exception (not corrupt |
| any of the heaps on which it operates), but joining two pairing |
| heaps is exception free.</p> |
| |
| <p>Tags and traits are very useful for manipulating generic |
| types. <a href= |
| "priority_queue.html"><tt>pb_ds::priority_queue</tt></a> |
| publicly defines <tt>container_category</tt> as one of the tags |
| discussed in <a href="#pq_imp">Implementations</a>. Given any |
| container <tt>Cntnr</tt>, the tag of the underlying |
| data structure can be found via <tt><b>typename</b> |
| Cntnr::container_category</tt>; this is one of the types shown in |
| Figure <a href="#pq_tag_cd">Data-structure tag class |
| hierarchy</a>.</p> |
| |
| <h6 class="c1"><a name="pq_tag_cd" id= |
| "pq_tag_cd"><img src="priority_queue_tag_cd.png" alt= |
| "no image" /></a></h6> |
| |
| <h6 class="c1">Data-structure tag class hierarchy.</h6> |
| |
| <p>Additionally, a traits mechanism can be used to query a |
| container type for its attributes. Given any container |
| <tt>Cntnr</tt>, then <tt><a href= |
| "assoc_container_traits.html">pb_ds::container_traits</a><Cntnr></tt> |
| is a traits class identifying the properties of the |
| container.</p> |
| |
| <p>To find if a container might throw if two of its objects are |
| joined, one can use <a href= |
| "assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::split_join_can_throw</tt>, |
| for example.</p> |
| |
| <p>Different priority-queue implementations have different invalidation guarantees. This is |
| especially important, since as explained in <a href= |
| "#pq_it">Iterators</a>, there is no way to access an arbitrary |
| value of priority queues except for iterators. Similarly to |
| associative containers, one can use |
| <a href= |
| "assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::invalidation_guarantee</tt> |
| to get the invalidation guarantee type of a priority queue.</p> |
| |
| <p>It is easy to understand from Figure <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a>, what <a href= |
| "assoc_container_traits.html"><tt>container_traits</tt></a><tt><Cntnr>::invalidation_guarantee</tt> |
| will be for different implementations. All implementations of |
| type <a href="#pq_different_underlying_dss">Underlying |
| Priority-Queue Data-Structures</a> B have <a href= |
| "point_invalidation_guarantee.html"><tt>point_invalidation_guarantee</tt></a>: |
| the container can freely internally reorganize the nodes - |
| range-type iterators are invalidated, but point-type iterators |
| are always valid. Implementations of type <a href= |
| "#pq_different_underlying_dss">Underlying Priority-Queue |
| Data-Structures</a> A1 and A2 have <a href= |
| "basic_invalidation_guarantee.html"><tt>basic_invalidation_guarantee</tt></a>: |
| the container can freely internally reallocate the array - both |
| point-type and range-type iterators might be invalidated.</p> |
| |
| <p>This has major implications, and constitutes a good reason to avoid |
| using binary heaps. A binary heap can perform <tt>modify</tt> |
| or <tt>erase</tt> efficiently <u>given a valid point-type |
| iterator</u>. However, inn order to supply it with a valid point-type |
| iterator, one needs to iterate (linearly) over all |
| values, then supply the relevant iterator (recall that a |
| range-type iterator can always be converted to a point-type |
| iterator). This means that if the number of <tt>modify</tt> or |
| <tt>erase</tt> operations is non-negligible (say |
| super-logarithmic in the total sequence of operations) - binary |
| heaps will perform badly.</p> |
| <pre> |
| |
| </pre> |
| </div> |
| </body> |
| </html> |