.
*/
/**
* A PriorityQueue maintains a partial ordering of its elements such that the
* least element can always be found in constant time. Put()'s and pop()'s
* require log(size) time.
*/
public class PriorityQueue {
private Comparable[] heap;
private int size;
private int maxSize;
public PriorityQueue(int maxSize) {
this.size = 0;
this.maxSize = maxSize;
heap = new Comparable[maxSize+2]; // 0th element is never used; Last element is temporarily used during put() to put a new element and pop an old one
}
/**
* Adds an Object to a PriorityQueue in log(size) time.
* If the PriorityQueue is not full, returns null.
* Otherwise, returns the popped object. This was
* the lowest object, which was removed in order to
* maintain the PriorityQueue constant.
*/
public final Object put(Comparable element) {
size++;
heap[size] = element;
upHeap();
if (size>maxSize) // if hit queue overfull
return pop(); // remove lowest in the queue
else
return null;
}
/** Returns the least element of the PriorityQueue in constant time. */
public final Object top() {
if (size > 0)
return heap[1];
else
return null;
}
/** Removes and returns the least element of the PriorityQueue in log(size)
time. */
public final Object pop() {
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;
}
/** 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); }
*

*/
public final void adjustTop() {
downHeap();
}
/** Returns the number of elements currently stored in the PriorityQueue. */
public final int size() {
return size;
}
/** Removes all entries from the PriorityQueue. */
public final void clear() {
for (int i = 0; i < heap.length; i++)
heap[i] = null;
size = 0;
}
private final void upHeap() {
int i = size;
Comparable node = heap[i]; // save bottom node
int j = i >>> 1;
while (j > 0 && node.compareTo(heap[j])<0) {
heap[i] = heap[j]; // shift parents down
i = j;
j = j >>> 1;
}
heap[i] = node; // install saved node
}
private final void downHeap() {
int i = 1;
Comparable node = heap[i]; // save top node
int j = i << 1; // find smaller child
int k = j + 1;
if (k <= size && heap[k].compareTo(heap[j])<0) {
j = k;
}
while (j <= size && heap[j].compareTo(node)<0) {
heap[i] = heap[j]; // shift up child
i = j;
j = i << 1;
k = j + 1;
if (k <= size && heap[k].compareTo(heap[j])<0) {
j = k;
}
}
heap[i] = node; // install saved node
}
public static void main(String[] args) {
int queueSize = 3;
PriorityQueue pq = new PriorityQueue(queueSize);
String s = null;
String[] strings = new String[] {"gggg", "ea", "cbbbbbb", "caaa", "d", "daaa", "db", "dccccccccc", "e", "cc"};
//print the test strings in ascending order:
java.util.List list = new java.util.LinkedList();
for(int i=0;i0);
}
}