| Constructors Summary |
|---|
public PriorityQueue()Constructs a priority queue with an initial capacity of 11 and natural
ordering.
this(DEFAULT_CAPACITY);
|
public PriorityQueue(int initialCapacity)Constructs a priority queue with the specified capacity and natural
ordering.
this(initialCapacity, null);
|
public PriorityQueue(int initialCapacity, Comparator comparator)Constructs a priority queue with the specified capacity and comparator.
if (initialCapacity < 1) {
throw new IllegalArgumentException();
}
elements = newElementArray(initialCapacity);
this.comparator = comparator;
|
public PriorityQueue(Collection c)Constructs a priority queue that contains the elements of a collection.
The constructed priority queue has the initial capacity of 110% of the
size of the collection. The queue uses natural ordering to order its
elements.
if (c instanceof PriorityQueue) {
getFromPriorityQueue((PriorityQueue<? extends E>) c);
} else if (c instanceof SortedSet) {
getFromSortedSet((SortedSet<? extends E>) c);
} else {
initSize(c);
addAll(c);
}
|
public PriorityQueue(PriorityQueue c)Constructs a priority queue that contains the elements of another
priority queue. The constructed priority queue has the initial capacity
of 110% of the specified one. Both priority queues have the same
comparator.
getFromPriorityQueue(c);
|
public PriorityQueue(SortedSet c)Constructs a priority queue that contains the elements of a sorted set.
The constructed priority queue has the initial capacity of 110% of the
size of the sorted set. The priority queue will have the same comparator
as the sorted set.
getFromSortedSet(c);
|
| Methods Summary |
|---|
| public boolean | add(E o)Adds the specified object to the priority queue.
return offer(o);
|
| public void | clear()Removes all the elements of the priority queue.
Arrays.fill(elements, null);
size = 0;
|
| public java.util.Comparator | comparator()Gets the comparator of the priority queue.
return comparator;
|
| private int | compare(E o1, E o2)
if (null != comparator) {
return comparator.compare(o1, o2);
}
return ((Comparable<? super E>) o1).compareTo(o2);
|
| private void | getFromPriorityQueue(java.util.PriorityQueue c)
initSize(c);
comparator = (Comparator<? super E>) c.comparator();
System.arraycopy(c.elements, 0, elements, 0, c.size());
size = c.size();
|
| private void | getFromSortedSet(java.util.SortedSet c)
initSize(c);
comparator = (Comparator<? super E>) c.comparator();
Iterator<? extends E> iter = c.iterator();
while (iter.hasNext()) {
elements[size++] = iter.next();
}
|
| private void | growToSize(int size)
if (size > elements.length) {
E[] newElements = newElementArray(size * DEFAULT_CAPACITY_RATIO);
System.arraycopy(elements, 0, newElements, 0, elements.length);
elements = newElements;
}
|
| private void | initSize(java.util.Collection c)
if (null == c) {
throw new NullPointerException();
}
if (c.isEmpty()) {
elements = newElementArray(1);
} else {
int capacity = (int) Math.ceil(c.size()
* DEFAULT_INIT_CAPACITY_RATIO);
elements = newElementArray(capacity);
}
|
| public java.util.Iterator | iterator()Gets the iterator of the priority queue, which will not return elements
in any specified ordering.
return new PriorityIterator();
|
| private E[] | newElementArray(int capacity)
return (E[]) new Object[capacity];
|
| public boolean | offer(E o)Inserts the element to the priority queue.
if (null == o) {
throw new NullPointerException();
}
growToSize(size + 1);
elements[size] = o;
siftUp(size++);
return true;
|
| public E | peek()Gets but does not remove the head of the queue.
if (isEmpty()) {
return null;
}
return elements[0];
|
| public E | poll()Gets and removes the head of the queue.
if (isEmpty()) {
return null;
}
E result = elements[0];
removeAt(0);
return result;
|
| private void | readObject(java.io.ObjectInputStream in)
in.defaultReadObject();
int capacity = in.readInt();
elements = newElementArray(capacity);
for (int i = 0; i < size; i++) {
elements[i] = (E) in.readObject();
}
|
| public boolean | remove(java.lang.Object o)Removes the specified object from the priority queue.
if (o == null) {
return false;
}
int targetIndex;
for (targetIndex = 0; targetIndex < size; targetIndex++) {
if (0 == this.compare((E) o, elements[targetIndex])) {
break;
}
}
if (size == 0 || size == targetIndex) {
return false;
}
removeAt(targetIndex);
return true;
|
| private void | removeAt(int index)
size--;
elements[index] = elements[size];
siftDown(index);
elements[size] = null;
|
| private void | siftDown(int rootIndex)
E target = elements[rootIndex];
int childIndex;
while ((childIndex = rootIndex * 2 + 1) < size) {
if (childIndex + 1 < size
&& compare(elements[childIndex + 1], elements[childIndex]) < 0) {
childIndex++;
}
if (compare(target, elements[childIndex]) <= 0) {
break;
}
elements[rootIndex] = elements[childIndex];
rootIndex = childIndex;
}
elements[rootIndex] = target;
|
| private void | siftUp(int childIndex)
E target = elements[childIndex];
int parentIndex;
while (childIndex > 0) {
parentIndex = (childIndex - 1) / 2;
E parent = elements[parentIndex];
if (compare(parent, target) <= 0) {
break;
}
elements[childIndex] = parent;
childIndex = parentIndex;
}
elements[childIndex] = target;
|
| public int | size()Gets the size of the priority queue. If the size of the queue is greater
than the Integer.MAX, then it returns Integer.MAX.
return size;
|
| private void | writeObject(java.io.ObjectOutputStream out)
out.defaultWriteObject();
out.writeInt(elements.length);
for (int i = 0; i < size; i++) {
out.writeObject(elements[i]);
}
|
