llvm-gcc-4.2/libstdc++-v3/docs/html/ext/pb_ds/pq_design.html - llvm-archive - Git at Google

 <!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>&lt;
     <b>typename</b> Value_Type,
     <b>typename</b> Cmp_Fn = std::less&lt;Value_Type&gt;,
     <b>typename</b> Tag = <a href="pairing_heap_tag.html">pairing_heap_tag</a>,
     <b>typename</b> Allocator = std::allocator&lt;<b>char</b>&gt; &gt;
 <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>&lt;<b>int</b>&gt; p;

 <i>// Insert some values into the priority queue.</i>
 <a href=
 "priority_queue.html">priority_queue</a>&lt;<b>int</b>&gt;::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>&lt;Cntnr&gt;</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>&lt;Cntnr&gt;::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>&lt;Cntnr&gt;::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>&lt;Cntnr&gt;::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>
	<!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>