Priority Queue
Priority Queue ADT
- A priority queue stores a collection of items
- An item is a pair (key, element)
- Main methods of the Priority Queue ADT
- insertItem(k, o): inserts an item with key k and element o
- removeMin(): removes the item with smallest key and returns its element
- Additional methods
- minKey(): returns, but does not remove, the smallest key of an item
- minElement(): returns, but does not remove, the element of an item with smallest key
- size(), isEmpty()
- Applications: Standby flyers, AuctionsStock market
- Total Order Relation
- Keys in a priority queue can be arbitrary objects on which an order is defined
- Two distinct items in a priority queue can have the same key
- Mathematical concept of total order relation ≤
- Reflexive property: x ≤ x
- Antisymmetric property: x ≤ y ∧ y ≤ x ⇒ x = y
- Transitive property: x ≤ y ∧ y ≤ z ⇒ x ≤ z
Comparator ADT
- A comparator encapsulates the action of comparing two objects according to a given total order relation
- A generic priority queue uses an auxiliary comparator
- The comparator is external to the keys being compared
- When the priority queue needs to compare two keys, it uses its comparator Methods of the Comparator ADT, all with Boolean return type:
- isLessThan(x, y)
- isLessThanOrEqualTo(x,y)
- isEqualTo(x,y)
- isGreaterThan(x, y)
- isGreaterThanOrEqualTo(x,y)
- isComparable(x)
Sorting with a Priority Queue
- We can use a priority queue to sort a set of comparable elements
- Insert the elements one by one with a series of insertItem(e, e) operations
- Remove the elements in sorted order with a series of removeMin() operations
- The running time of this sorting method depends on the priority queue implementation
Algorithm PQ-Sort(S, C)
Input sequence S, comparator C
for the elements of S
Output sequence S sorted in
increasing order according to C
P ← priority queue with comparator C
while ¬S.isEmpty ()
e ← S.remove (S. first ())
P.insertItem(e, e)
while ¬P.isEmpty()
e ← P.removeMin()
S.insertLast(e)
Sequence-based Priority Queue
- Implementation with an unsorted list
- Performance:
- insertItem takes O(1) time since we can insert the item at the beginning or end of the sequence
- removeMin, minKey and minElement take O(n) time since we have to traverse the entire sequence to find the smallest key
- Implementation with a sorted list
- Performance:
- insertItem takes O(n) time since we have to find the place where to insert the item
- removeMin, minKey and minElement take O(1) time since the smallest key is at the beginning of the sequence
Section-Sort
- Selection-sort is the variation of PQ-sort where the priority queue is implemented with an unsorted sequence
- Running time of Selection-sort:
- Inserting the elements into the priority queue with n insertItem operations takes O(n) time
- Removing the elements in sorted order from the priority queue with n removeMin operations takes time proportional to 1 + 2 + …+ n
- Selection-sort runs in O(n^2) time
Insertion-sort
- Insertion-sort is the variation of PQ-sort where the priority queue is implemented with a sorted sequence
- Running time of Insertion-sort:
- Inserting the elements into the priority queue with n insertItem operations takes time proportional to 1 + 2 + …+ n
- Removing the elements in sorted order from the priority queue with a series of n removeMin operations takes O(n) time
- Insertion-sort runs in O(n^2) time
In-place Insertion-sort
- Instead of using an external data structure, we can implement selection-sort and insertion-sort in-place
- A portion of the input sequence itself serves as the priority queue
- For in-place insertion-sort
- We keep sorted the initial portion of the sequence
- We can use swapElements instead of modifying the sequence
package examples;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Hashtable;
public class MyPriorityQueue<K extends Comparable<? super K>, E> implements
PriorityQueue<K, E> {
class PQLoc<K1 extends Comparable<? super K1>,E1>
implements Locator<K1 , E1>{
E1 elem;
K1 key;
Object creator = MyPriorityQueue.this;
int pos;
@Override
public E1 element() {
return elem;
}
@Override
public K1 key() {
return key;
}
}
private PQLoc<K,E> [] stor =(PQLoc<K,E>[]) new PQLoc[256];
private int size;
private PQLoc<K,E> castToLNode(Locator<K,E> p){
PQLoc<K,E> n;
try {
n = (PQLoc<K,E>) p;
} catch (ClassCastException e) {
throw new RuntimeException("This is not a Locator belonging to MyPriorityQueue");
}
if (n.creator == null) throw new RuntimeException("locator was allready deleted!");
if (n.creator != this) throw new RuntimeException("locator belongs to another PriorityQueue!");
return n;
}
@Override
public Locator<K, E> showMin() {
if (size == 0) return null;
return stor[1];
}
@Override
public Locator<K, E> removeMin() {
if (size==0) return null;
PQLoc<K,E> n = stor[1];
remove(n);
return n;
}
@Override
public Locator<K, E> insert(K key, E element) {
PQLoc<K,E> loc = new PQLoc<>();
loc.elem = element;
loc.key=key;
if (size == stor.length-1) {
stor = Arrays.copyOf(stor,stor.length*2);
}
stor[++size]=loc;
loc.pos = size;
upHeap(size);
return loc;
}
private void upHeap(int i) {
while (i > 1 && stor[i].key.compareTo(stor[i/2].key) < 0){
swap(i,i/2);
i=i/2;
}
}
private void downHeap(int i) {
int left = i*2;
while (left <= size){
int right = left+1;
int cand = left;
if (right < size &&
stor[left].key.compareTo(stor[right].key) > 0) cand = right;
if (stor[i].key.compareTo(stor[cand].key) <= 0) break;
swap(i,cand);
i=cand;
left=i*2;
}
}
private void swap(int i, int k) {
PQLoc<K,E> tmp = stor[i];
stor[i]=stor[k];
stor[k]=tmp;
stor[i].pos=i;
stor[k].pos=k;
}
@Override
public void remove(Locator<K, E> loc) {
PQLoc<K,E> n = castToLNode(loc);
PQLoc<K,E> n2 = stor[size];
swap(n.pos,size--);
upHeap(n2.pos);
downHeap(n2.pos);
n.creator = null;
}
@Override
public void replaceKey(Locator<K, E> loc, K newKey) {
PQLoc<K,E> n = castToLNode(loc);
n.key = newKey;
upHeap(n.pos);
downHeap(n.pos);
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
public static void main(String[] args) {
PriorityQueue<Integer,String> pq = new MyPriorityQueue<>();
pq.insert(7,"bla");
pq.insert(11,"bla");
pq.insert(5,"bla");
Locator<Integer,String > l = pq.insert(14,"bla");
pq.insert(6,"bla");
pq.insert(20,"bla");
pq.remove(l);
System.out.println(pq.removeMin().key());
System.out.println(pq.removeMin().key());
System.out.println(pq.removeMin().key());
System.out.println(pq.removeMin().key());
System.out.println(pq.removeMin().key());
java.util.Random rand = new java.util.Random();
int n = 10000000;
long start = System.nanoTime();
for (int i=0;i<n;i++) pq.insert(n-i,null);
for (int i=0;i<n;i++) {
pq.removeMin();
}
long end = System.nanoTime();
System.out.println("elapsed time: "+(end-start)/1.e9+" s for "+n+" locators");
Hashtable z;
}
}