PriorityQueue

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> edu >> emory >> mathcs >> [ util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

Sourc code of edu.emory.mathcs.util.PriorityQueue

SOURCE |

Download edu.emory.mathcs.util.PriorityQueue

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

edu.emory.mathcs.util
Class PriorityQueue

java.lang.Object
  java.util.AbstractCollection
      edu.emory.mathcs.util.AbstractQueue
          edu.emory.mathcs.util.PriorityQueue

All Implemented Interfaces:: java.util.Collection, java.lang.Iterable, Queue, java.io.Serializable

public class PriorityQueue
extends AbstractQueue
implements Queue, java.io.Serializable

An unbounded priority queue based on a priority heap. This queue orders elements according to an order specified at construction time, which is specified in the same manner as java.util.TreeSet and java.util.TreeMap: elements are ordered either according to their natural order (see java.lang.Comparable), or according to a java.util.Comparator, depending on which constructor is used. The peek() 55 , poll() 55 , and remove(java.lang.Object) 55 methods return the minimal element with respect to the specified ordering. If multiple elements are tied for least value, no guarantees are made as to which of these elements is returned.

A priority queue has a capacity. The capacity is the size of the array used internally 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.

Implementation note: this implementation provides O(log(n)) time for the insertion methods (offer, poll, remove() and add) methods; linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

This class is a member of the Java Collections Framework.

Since:: 1.5

Nested Class Summary

private class PriorityQueue.Itr


Field Summary

private java.util.Comparator comparator
          The comparator, or null if priority queue uses elements' natural ordering.

private static int DEFAULT_INITIAL_CAPACITY


private int modCount
          The number of times this priority queue has been structurally modified.

private java.lang.Object[] queue
          Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n] and queue[2*n + 1].

private int size
          The number of elements in the priority queue.

Constructor Summary

PriorityQueue()
          Create a new priority queue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable.)

PriorityQueue(java.util.Collection initialElements)
          Create a new priority queue containing the elements in the specified collection.

PriorityQueue(int initialCapacity)
          Create a new priority queue with the specified initial capacity that orders its elements according to their natural ordering (using Comparable.)

PriorityQueue(int initialCapacity, java.util.Comparator comparator)
          Create a new priority queue with the specified initial capacity (11) that orders its elements according to the specified comparator.

Method Summary

void clear()
          Remove all elements from the priority queue.

java.util.Comparator comparator()
          Returns the comparator associated with this priority queue, or null if it uses its elements' natural ordering.

private void fixDown(int k)
          Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may be greater than its children).

private void fixUp(int k)
          Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leaf-node indexed by k (which may have a nextExecutionTime less than its parent's).

java.util.Iterator iterator()
          Returns an iterator over the elements in this priority queue.

boolean offer(java.lang.Object element)
          Add the specified element to this priority queue.

java.lang.Object peek()
          Return, but do not remove, the minimal element from the priority queue, or return null if the queue is empty.

java.lang.Object poll()
          Remove and return the minimal element from this priority queue if it contains one or more elements, otherwise return null.

private void readObject(java.io.ObjectInputStream s)
          Reconstitute the ArrayList instance from a stream (that is, deserialize it).

private java.lang.Object remove(int i)
          Removes and returns the ith element from queue.

boolean remove(java.lang.Object element)
          Removes a single instance of the specified element from this priority queue, if it is present.

int size()
          Returns the number of elements in this priority queue.

private void writeObject(java.io.ObjectOutputStream s)
          Save the state of the instance to a stream (that is, serialize it).

Methods inherited from class edu.emory.mathcs.util.AbstractQueue

add, element, remove

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface edu.emory.mathcs.util.Queue

element, remove

Methods inherited from interface java.util.Collection

add, addAll, contains, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

Field Detail

DEFAULT_INITIAL_CAPACITY

private static final int DEFAULT_INITIAL_CAPACITY

See Also:: Constant Field Values

queue

private transient java.lang.Object[] queue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n] and queue[2*n + 1]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[1], assuming the queue is nonempty. (A one-based array is used in preference to the traditional zero-based array to simplify parent and child calculations.) queue.length must be >= 2, even if size == 0.

size

private int size

The number of elements in the priority queue.

comparator

private final java.util.Comparator comparator

The comparator, or null if priority queue uses elements' natural ordering.

modCount

private transient int modCount

The number of times this priority queue has been structurally modified. See AbstractList for gory details.

Constructor Detail

PriorityQueue

public PriorityQueue()

Create a new priority queue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable.)

PriorityQueue

public PriorityQueue(int initialCapacity)

Create a new priority queue with the specified initial capacity that orders its elements according to their natural ordering (using Comparable.)

PriorityQueue

public PriorityQueue(int initialCapacity,
                     java.util.Comparator comparator)

Create a new priority queue with the specified initial capacity (11) that orders its elements according to the specified comparator.

PriorityQueue

public PriorityQueue(java.util.Collection initialElements)

Create a new priority queue containing the elements in the specified collection. The priority queue has an initial capacity of 110% of the size of the specified collection. If the specified collection implements the Sorted interface, the priority queue will be sorted according to the same comparator, or according to its elements' natural order if the collection is sorted according to its elements' natural order. If the specified collection does not implement Sorted, the priority queue is ordered according to its elements' natural order.

Method Detail

poll

public java.lang.Object poll()

Remove and return the minimal element from this priority queue if it contains one or more elements, otherwise return null. The term minimal is defined according to this priority queue's order.

Specified by:: poll in interface Queue

peek

public java.lang.Object peek()

Return, but do not remove, the minimal element from the priority queue, or return null if the queue is empty. The term minimal is defined according to this priority queue's order. This method returns the same object reference that would be returned by by the poll method. The two methods differ in that this method does not remove the element from the priority queue.

Specified by:: peek in interface Queue

remove

public boolean remove(java.lang.Object element)

Removes a single instance of the specified element from this priority queue, if it is present. Returns true if this collection contained the specified element (or equivalently, if this collection changed as a result of the call).

Specified by:: remove in interface java.util.Collection

iterator

public java.util.Iterator iterator()

Returns an iterator over the elements in this priority queue. The elements of the priority queue will be returned by this iterator in the order specified by the queue, which is to say the order they would be returned by repeated calls to poll.

Specified by:: iterator in interface java.util.Collection

size

public int size()

Returns the number of elements in this priority queue.

Specified by:: size in interface java.util.Collection

offer

public boolean offer(java.lang.Object element)

Add the specified element to this priority queue.

Specified by:: offer in interface Queue

clear

public void clear()

Remove all elements from the priority queue.

Specified by:: clear in interface java.util.Collection
Overrides:: clear in class AbstractQueue

remove

private java.lang.Object remove(int i)

Removes and returns the ith element from queue. Recall that queue is one-based, so 1 <= i <= size. XXX: Could further special-case i==size, but is it worth it? XXX: Could special-case i==0, but is it worth it?

fixUp

private void fixUp(int k)

Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leaf-node indexed by k (which may have a nextExecutionTime less than its parent's). This method functions by "promoting" queue[k] up the hierarchy (by swapping it with its parent) repeatedly until queue[k] is greater than or equal to its parent.

fixDown

private void fixDown(int k)

Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may be greater than its children). This method functions by "demoting" queue[k] down the hierarchy (by swapping it with its smaller child) repeatedly until queue[k] is less than or equal to its children.

comparator

public java.util.Comparator comparator()

Returns the comparator associated with this priority queue, or null if it uses its elements' natural ordering.

writeObject

private void writeObject(java.io.ObjectOutputStream s)
                  throws java.io.IOException

Save the state of the instance to a stream (that is, serialize it).

readObject

private void readObject(java.io.ObjectInputStream s)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Reconstitute the ArrayList instance from a stream (that is, deserialize it).

Overview

Package

Class

Use

Deprecated

Index

Home >> All >> edu >> emory >> mathcs >> [ util overview ]

PREV CLASS NEXT CLASS

SUMMARY:

JAVADOC |

SOURCE |

DOWNLOAD | NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Field Summary
`private java.util.Comparator`	`comparator` The comparator, or null if priority queue uses elements' natural ordering.
`private static int`	`DEFAULT_INITIAL_CAPACITY`
`private int`	`modCount` The number of times this priority queue has been structurally modified.
`private java.lang.Object[]`	`queue` Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n] and queue[2n + 1].
`private int`	`size` The number of elements in the priority queue.

Constructor Summary
`PriorityQueue()` Create a new priority queue with the default initial capacity (11) that orders its elements according to their natural ordering (using `Comparable`.)
`PriorityQueue(java.util.Collection initialElements)` Create a new priority queue containing the elements in the specified collection.
`PriorityQueue(int initialCapacity)` Create a new priority queue with the specified initial capacity that orders its elements according to their natural ordering (using `Comparable`.)
`PriorityQueue(int initialCapacity, java.util.Comparator comparator)` Create a new priority queue with the specified initial capacity (11) that orders its elements according to the specified comparator.

Method Summary
`void`	`clear()` Remove all elements from the priority queue.
`java.util.Comparator`	`comparator()` Returns the comparator associated with this priority queue, or `null` if it uses its elements' natural ordering.
`private void`	`fixDown(int k)` Establishes the heap invariant (described above) in the subtree rooted at k, which is assumed to satisfy the heap invariant except possibly for node k itself (which may be greater than its children).
`private void`	`fixUp(int k)` Establishes the heap invariant (described above) assuming the heap satisfies the invariant except possibly for the leaf-node indexed by k (which may have a nextExecutionTime less than its parent's).
`java.util.Iterator`	`iterator()` Returns an iterator over the elements in this priority queue.
`boolean`	`offer(java.lang.Object element)` Add the specified element to this priority queue.
`java.lang.Object`	`peek()` Return, but do not remove, the minimal element from the priority queue, or return `null` if the queue is empty.
`java.lang.Object`	`poll()` Remove and return the minimal element from this priority queue if it contains one or more elements, otherwise return `null`.
`private void`	`readObject(java.io.ObjectInputStream s)` Reconstitute the `ArrayList` instance from a stream (that is, deserialize it).
`private java.lang.Object`	`remove(int i)` Removes and returns the ith element from queue.
`boolean`	`remove(java.lang.Object element)` Removes a single instance of the specified element from this priority queue, if it is present.
`int`	`size()` Returns the number of elements in this priority queue.
`private void`	`writeObject(java.io.ObjectOutputStream s)` Save the state of the instance to a stream (that is, serialize it).

edu.emory.mathcs.util Class PriorityQueue

DEFAULT_INITIAL_CAPACITY

queue

size

comparator

modCount

PriorityQueue

PriorityQueue

PriorityQueue

PriorityQueue

poll

peek

remove

iterator

size

offer

clear

remove

fixUp

fixDown

comparator

writeObject

readObject

edu.emory.mathcs.util
Class PriorityQueue