[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.5, Tue May 27 18:20:06 2003 UTC revision 1.6, Mon Jun 23 02:26:15 2003 UTC
# Line 2  Line 2 
2    
3  /**  /**
4   * An unbounded priority queue based on a priority heap.  This queue orders   * An unbounded priority queue based on a priority heap.  This queue orders
5   * elements according to the order specified at creation time.  This order is   * elements according to an order specified at construction time, which is
6   * specified as for {@link TreeSet} and {@link TreeMap}: Elements are ordered   * specified in the same manner as {@link TreeSet} and {@link TreeMap}: elements are ordered
7   * either according to their <i>natural order</i> (see {@link Comparable}), or   * either according to their <i>natural order</i> (see {@link Comparable}), or
8   * according to a {@link Comparator}, depending on which constructor is used.   * according to a {@link Comparator}, depending on which constructor is used.
9   * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the   * The {@link #peek}, {@link #poll}, and {@link #remove} methods return the
10   * minimal element with respect to the specified ordering.  If multiple   * minimal element with respect to the specified ordering.  If multiple
11   * these elements are tied for least value, no guarantees are made as to   * elements are tied for least value, no guarantees are made as to
12   * which of elements is returned.   * which of these elements is returned.
13   *   *
14   * <p>Each priority queue has a <i>capacity</i>.  The capacity is the size of   * <p>A priority queue has a <i>capacity</i>.  The capacity is the size of
15   * the array used to store the elements on the queue.  It is always at least   * the array used internally to store the elements on the queue.  It is always at least
16   * as large as the queue size.  As elements are added to a priority list,   * as large as the queue size.  As elements are added to a priority queue,
17   * its capacity grows automatically.  The details of the growth policy are not   * its capacity grows automatically.  The details of the growth policy are not
18   * specified.   * specified.
19   *   *
20   *<p>Implementation note: this implementation provides O(log(n)) time for   *<p>Implementation note: this implementation provides O(log(n)) time for
21   * the <tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>   * the insertion methods (<tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>)
22   * methods; linear time for the <tt>remove(Object)</tt> and   * methods; linear time for the <tt>remove(Object)</tt> and
23   * <tt>contains</tt> methods; and constant time for the <tt>peek</tt>,   * <tt>contains(Object)</tt> methods; and constant time for the retrieval methods (<tt>peek</tt>,
24   * <tt>element</tt>, and <tt>size</tt> methods.   * <tt>element</tt>, and <tt>size</tt>).
25   *   *
26   * <p>This class is a member of the   * <p>This class is a member of the
27   * <a href="{@docRoot}/../guide/collections/index.html">   * <a href="{@docRoot}/../guide/collections/index.html">
# Line 36  Line 36 
36       * Priority queue represented as a balanced binary heap: the two children       * Priority queue represented as a balanced binary heap: the two children
37       * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is       * of queue[n] are queue[2*n] and queue[2*n + 1].  The priority queue is
38       * ordered by comparator, or by the elements' natural ordering, if       * ordered by comparator, or by the elements' natural ordering, if
39       * comparator is null:  For each node n in the heap, and each descendant       * comparator is null:  For each node n in the heap and each descendant d
40       * of n, d, n <= d.       * of n, n <= d.
41       *       *
42       * The element with the lowest value is in queue[1] (assuming the queue is       * The element with the lowest value is in queue[1], assuming the queue is
43       * nonempty). A one-based array is used in preference to the traditional       * nonempty.  (A one-based array is used in preference to the traditional
44       * zero-based array to simplify parent and child calculations.       * zero-based array to simplify parent and child calculations.)
45       *       *
46       * queue.length must be >= 2, even if size == 0.       * queue.length must be >= 2, even if size == 0.
47       */       */
# Line 66  Line 66 
66    
67      /**      /**
68       * Create a new priority queue with the default initial capacity (11)       * Create a new priority queue with the default initial capacity (11)
69       * that orders its elements according to their natural ordering.       * that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)
70       */       */
71      public PriorityQueue() {      public PriorityQueue() {
72          this(DEFAULT_INITIAL_CAPACITY);          this(DEFAULT_INITIAL_CAPACITY);
# Line 74  Line 74 
74    
75      /**      /**
76       * Create a new priority queue with the specified initial capacity       * Create a new priority queue with the specified initial capacity
77       * that orders its elements according to their natural ordering.       * that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)
78       *       *
79       * @param initialCapacity the initial capacity for this priority queue.       * @param initialCapacity the initial capacity for this priority queue.
80       */       */
# Line 103  Line 103 
103       * implements the {@link Sorted} interface, the priority queue will be       * implements the {@link Sorted} interface, the priority queue will be
104       * sorted according to the same comparator, or according to its elements'       * sorted according to the same comparator, or according to its elements'
105       * natural order if the collection is sorted according to its elements'       * natural order if the collection is sorted according to its elements'
106       * natural order.  If the specified collection does not implement the       * natural order.  If the specified collection does not implement
107       * <tt>Sorted</tt> interface, the priority queue is ordered according to       * <tt>Sorted</tt>, the priority queue is ordered according to
108       * its elements' natural order.       * its elements' natural order.
109       *       *
110       * @param initialElements the collection whose elements are to be placed       * @param initialElements the collection whose elements are to be placed
# Line 142  Line 142 
142    
143      /**      /**
144       * Remove and return the minimal element from this priority queue if       * Remove and return the minimal element from this priority queue if
145       * it contains one or more elements, otherwise <tt>null</tt>.  The term       * it contains one or more elements, otherwise return <tt>null</tt>.  The term
146       * <i>minimal</i> is defined according to this priority queue's order.       * <i>minimal</i> is defined according to this priority queue's order.
147       *       *
148       * @return the minimal element from this priority queue if it contains       * @return the minimal element from this priority queue if it contains
# Line 156  Line 156 
156    
157      /**      /**
158       * Return, but do not remove, the minimal element from the priority queue,       * Return, but do not remove, the minimal element from the priority queue,
159       * or <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is       * or return <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is
160       * defined according to this priority queue's order.  This method returns       * defined according to this priority queue's order.  This method returns
161       * the same object reference that would be returned by by the       * the same object reference that would be returned by by the
162       * <tt>poll</tt> method.  The two methods differ in that this method       * <tt>poll</tt> method.  The two methods differ in that this method
# Line 177  Line 177 
177       * specified element (or equivalently, if this collection changed as a       * specified element (or equivalently, if this collection changed as a
178       * result of the call).       * result of the call).
179       *       *
180       * @param o element to be removed from this collection, if present.       * @param element the element to be removed from this collection, if present.
181       * @return <tt>true</tt> if this collection changed as a result of the       * @return <tt>true</tt> if this collection changed as a result of the
182       *         call       *         call
183       * @throws ClassCastException if the specified element cannot be compared       * @throws ClassCastException if the specified element cannot be compared
# Line 209  Line 209 
209    
210      /**      /**
211       * Returns an iterator over the elements in this priority queue.  The       * Returns an iterator over the elements in this priority queue.  The
212       * first element returned by this iterator is the same element that       * elements of the priority queue will be returned by this iterator in the
213       * would be returned by a call to <tt>peek</tt>.       * order specified by the queue, which is to say the order they would be
214         * returned by repeated calls to <tt>poll</tt>.
215       *       *
216       * @return an <tt>Iterator</tt> over the elements in this priority queue.       * @return an <tt>Iterator</tt> over the elements in this priority queue.
217       */       */

Legend:
Removed from v.1.5  
changed lines
  Added in v.1.6

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8