While this queue is logically unbounded, attempted additions may fail due to resource exhaustion (causing OutOfMemoryError). This class does not permit null elements. A priority queue relying on {@linkplain Comparable natural ordering} also does not permit insertion ofnon-comparable objects (doing so results in ClassCastException).
This class and its iterator implement all of the optional methods of the {@link Collection} and {@link Iterator} interfaces. The Iterator provided in method {@link #iterator()} is not guaranteed to traverse the elements ofthe PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).
Operations on this class make no guarantees about the ordering of elements with equal priority. If you need to enforce an ordering, you can define custom classes or comparators that use a secondary key to break ties in primary priority values. See {@link edu.emory.mathcs.backport.java.util.concurrent.PriorityBlockingQueue}for an example.
Implementation note: basic mutative methods (insert, offer, remove, poll etc) have complexity O(log(n)). Parameterless inspection methods (peek, element,isEmpty) have complexity O(1). Methods contains(Object) and remove(Object) have complexity O(n). @since 1.5 @author Dawid Kurzyniec
The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations {@code poll}, {@code remove}, {@code peek}, and {@code element} access theelement at the head of the queue.
A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.
This class and its iterator implement all of the optional methods of the {@link Collection} and {@link Iterator} interfaces. The Iterator provided in method {@link #iterator()} is not guaranteed to traverse the elements ofthe priority queue in any particular order. If you need ordered traversal, consider using {@code Arrays.sort(pq.toArray())}.
Note that this implementation is not synchronized. Multiple threads should not access a {@code PriorityQueue}instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe {@link java.util.concurrent.PriorityBlockingQueue} class.
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods ( {@code offer}, {@code poll}, {@code remove()} and {@code add}); linear time for the {@code remove(Object)} and {@code contains(Object)}methods; and constant time for the retrieval methods ( {@code peek}, {@code element}, and {@code size}).
This class is a member of the Java Collections Framework. @since 1.5 @version 1.16, 04/21/06 @author Josh Bloch, Doug Lea @param < E> the type of elements held in this collection
Priority Queue that stores values as ints and priorities as floats. Uses a Heap to sort the priorities; the values are sorted "in step" with the priorities.
A Heap is simply an array that is kept semi sorted; in particular if the elements of the array are arranged in a tree structure; ie
00 / \ 01 02 / \ / \ 03 04 05 06 /\ /\ /\ /\ 07 08 09 10 11 12 13 14
then each parent is kept sorted with respect to it's immediate children. E.g. 00 < 01, 00 < 02, 02 < 05, 02 < 06
This means that the array appears to be sorted, as long as we only ever look at element 0.
Inserting new elements is much faster than if the entire array was kept sorted; a new element is appended to the array, and then recursively swapped with each parent to maintain the "parent is sorted w.r.t it's children" property.
To return the "next" value it is necessary to remove the root element. The last element in the array is placed in the root of the tree, and is recursively swapped with one of it's children until the "parent is sorted w.r.t it's children" property is restored.
Random access is slow (eg for deleting a particular value), and is not implemented here - if this functionality is required, then a heap probably isn't the right data structure.
NOTE: This class pre-allocates a full array of length maxSize+1, in {@link #initialize}.
Buffer that provides for removal based on Comparator ordering. The removal order of a binary heap is based on either the natural sort order of its elements or a specified {@linkComparator}. The {@link #remove()}method always returns the first element as determined by the sort order. (The ascendingOrder flag in the constructors can be used to reverse the sort order, in which case {@link #remove()}will always remove the last element.) The removal order is not the same as the order of iteration; elements are returned by the iterator in no particular order. The {@link #add(Object)}and {@link #remove()}operations perform in logarithmic time. The {@link #get()}operation performs in constant time. All other operations perform in linear time or worse. Note that this implementation is not synchronized.
@author Peter Donald
@author Ram Chidambaram
@author Michael A. Smith
@author Paul Jack
@author Stephen Colebourne
@author Simon Harris
@version $Revision: 1.2 $ $Date: 2004/11/19 02:15:18 $
PriorityQueue.java
Authors: Rainer Holzmann, Zhanna Melnikova-Albrecht, Matthias Schubert
Date: Aug 27, 2004
Time: 5:36:35 PM
$ Revision 1.4 $
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |