| Methods Summary |
|---|
| public final void | adjustTop()Should be called when the Object at top changes values. Still log(n)
worst case, but it's at least twice as fast to
{ pq.top().change(); pq.adjustTop(); }
instead of
{ o = pq.pop(); o.change(); pq.push(o); }
downHeap();
|
| public final void | clear()Removes all entries from the PriorityQueue.
for (int i = 0; i <= size; i++)
heap[i] = null;
size = 0;
|
| private final void | downHeap()
int i = 1;
Object node = heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
if (k <= size && lessThan(heap[k], heap[j])) {
j = k;
}
while (j <= size && lessThan(heap[j], node)) {
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
if (k <= size && lessThan(heap[k], heap[j])) {
j = k;
}
}
heap[i] = node; // install saved node
|
| protected final void | initialize(int maxSize)Subclass constructors must call this.
size = 0;
int heapSize = maxSize + 1;
heap = new Object[heapSize];
this.maxSize = maxSize;
|
| public boolean | insert(java.lang.Object element)Adds element to the PriorityQueue in log(size) time if either
the PriorityQueue is not full, or not lessThan(element, top()).
if(size < maxSize){
put(element);
return true;
}
else if(size > 0 && !lessThan(element, top())){
heap[1] = element;
adjustTop();
return true;
}
else
return false;
|
| protected abstract boolean | lessThan(java.lang.Object a, java.lang.Object b)Determines the ordering of objects in this priority queue. Subclasses
must define this one method.
|
| public final java.lang.Object | pop()Removes and returns the least element of the PriorityQueue in log(size)
time.
if (size > 0) {
Object result = heap[1]; // save first value
heap[1] = heap[size]; // move last to first
heap[size] = null; // permit GC of objects
size--;
downHeap(); // adjust heap
return result;
} else
return null;
|
| public final void | put(java.lang.Object element)Adds an Object to a PriorityQueue in log(size) time.
If one tries to add more objects than maxSize from initialize
a RuntimeException (ArrayIndexOutOfBound) is thrown.
size++;
heap[size] = element;
upHeap();
|
| public final int | size()Returns the number of elements currently stored in the PriorityQueue.
return size;
|
| public final java.lang.Object | top()Returns the least element of the PriorityQueue in constant time.
if (size > 0)
return heap[1];
else
return null;
|
| private final void | upHeap()
int i = size;
Object node = heap[i]; // save bottom node
int j = i >>> 1;
while (j > 0 && lessThan(node, heap[j])) {
heap[i] = heap[j]; // shift parents down
i = j;
j = j >>> 1;
}
heap[i] = node; // install saved node
|
