public abstract class PriorityQueue
extends Object
Modifier and Type | Field and Description |
---|---|
private boolean |
expandable |
private Object[] |
heap |
private int |
maxSize |
private int |
size |
Constructor and Description |
---|
PriorityQueue() |
Modifier and Type | Method and Description |
---|---|
void |
adjustTop()
Should be called when the Object at top changes values.
|
void |
clear()
Removes all entries from the PriorityQueue.
|
private void |
downHeap() |
private void |
expand()
Make the queue bigger.
|
protected void |
initialize(int maxSize)
Subclass constructors must call this.
|
boolean |
insert(Object element)
Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()).
|
protected abstract boolean |
lessThan(Object a,
Object b)
Determines the ordering of objects in this priority queue.
|
Object |
pop()
Removes and returns the least element of the PriorityQueue in log(size)
time.
|
void |
put(Object element)
Adds an Object to a PriorityQueue in log(size) time.
|
void |
setExpandable()
Make the queue expandable (will resize if full)
|
int |
size()
Returns the number of elements currently stored in the PriorityQueue.
|
Object |
top()
Returns the least element of the PriorityQueue in constant time.
|
private void |
upHeap() |
private Object[] heap
private int size
private int maxSize
private boolean expandable
protected abstract boolean lessThan(Object a, Object b)
protected final void initialize(int maxSize)
public void setExpandable()
private void expand()
public final void put(Object element)
public boolean insert(Object element)
element
- public final Object top()
public final Object pop()
public final void adjustTop()
{ pq.top().change(); pq.adjustTop(); }instead of
{ o = pq.pop(); o.change(); pq.push(o); }
public final int size()
public final void clear()
private final void upHeap()
private final void downHeap()