Package arc.struct

Class PQueue<E>

java.lang.Object

arc.struct.PQueue<E>

public class PQueue<E>
extends Object

A priority queue.

Field Summary

Fields

Modifier and Type	Field	Description
Comparator<E>	comparator	Function used for comparisons.
Object[]	queue	Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)].
int	size	The number of elements in the priority queue.

Constructor Summary

Constructors

Constructor	Description
PQueue()	Creates a PriorityQueue with the default initial capacity that orders its elements according to their natural ordering.
PQueue(int initialCapacity, Comparator<E> comparator)	Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

Method Summary

Modifier and Type	Method	Description
boolean	add(E e)	Inserts the specified element into this priority queue.
void	clear()	Removes all of the elements from this priority queue.
boolean	empty()
E	get(int index)	Retrieves the element at the specified index.
E	peek()	Retrieves, but does not remove, the head of this queue.
E	poll()	Retrieves and removes the head of this queue, or returns null if this queue is empty.
int	size()	Returns the number of elements in this queue.

Methods inherited from class java.lang.Object

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

Field Details

queue

public Object[] queue

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The priority queue is ordered by the elements' natural ordering: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

size

public int size

The number of elements in the priority queue.

comparator

public Comparator<E> comparator

Function used for comparisons.

Constructor Details

PQueue

public PQueue()

Creates a PriorityQueue with the default initial capacity that orders its elements according to their natural ordering.

PQueue

public PQueue(int initialCapacity,
 Comparator<E> comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

Parameters:

initialCapacity - the initial capacity for this priority queue

Method Details

empty

public boolean empty()

add

public boolean add(E e)

Inserts the specified element into this priority queue.

Returns:

true if the element was added to this queue, else false

Throws:

ClassCastException - if the specified element cannot be compared with elements currently in this priority queue according to the priority queue's ordering

IllegalArgumentException - if the specified element is null

peek

public E peek()

Retrieves, but does not remove, the head of this queue. If this queue is empty null is returned.

Returns:

the head of this queue

get

public E get(int index)

Retrieves the element at the specified index. If such an element doesn't exist null is returned.

Iterating the queue by index is not guaranteed to traverse the elements in any particular order.

Returns:

the element at the specified index in this queue.

size

public int size()

Returns the number of elements in this queue.

clear

public void clear()

Removes all of the elements from this priority queue. The queue will be empty after this call returns.

poll

public E poll()

Retrieves and removes the head of this queue, or returns null if this queue is empty.

Returns:

the head of this queue, or null if this queue is empty.