- A Priority Queue ranks its elements by key with a total order relation.
- Keys:
- Every element has its own key.
- Keys are not necessarily unique.
- A key is often a numerical value but the concept is general, i.e., not limited to numerics.
- Total Order Relation
- Denoted by £ .
- Reflexive:k£k.
- Antisymetric: if k1£k2 and k2£k1 then k1 = k2.
- Transitive: if k1£k2 and k2£k3 then k1£k3.
- A Priority Queue supports these fundamental methods:
- insertItem(Object k, Object e)
- Object removeMinElement()
Sorting with a Priority Queue
- A Priority Queue P can be used for sorting by inserting a Sequence S of n elements and calling removeMinElement until P is empty.
Input: A sequence S storing n keys, on which a total order relation is defined, and a Priority Queue P that compares keys with the same relation. Output: The Sequence S sorted by the total order relation. while !S.isEmpty() do e ¬S.removeFirst()
P.insertItem(e,e)
while !P.isEmpty() do
e ¬ P.removeMinElement()
S.insertLast(e)
The Priority Queue ADT
- A Priority Queue ADT must support the following methods:
- size():
- Return the number of elements in P.Input: None; Output:
integer
- isEmpty():
- insertItem(k,e):
- Test whether P is empty.Input: None; Output: boolean
- Insert a new element e with key k into
P.Input: Objects k,e; Output:
none
- minElement():
- Return but don’t remove an element of P with smallest
key; an error occurs if P is empty.Input: none: Output: Object e
The Priority Queue ADT (cont.)
- minKey():
- Return the smallest key in P; an error occurs
if P is empty.Input: none; Output: Object k
- removeMinElement():
- Remove from P and return an element with the smallest
key; an error condition occurs if P is empty.Input: none; Output: Object e
public class
Item {
private Object key, elem;
private Object key, elem;
public Item (Object k, Object e) {
key = k;
elem = e;
}
key = k;
elem = e;
}
public Object key() { return key; }
public Object element() { return elem; }
public void setKey(Object k) { key = k; }
public void setElement(Object e) { elem = e; }
}
public Object element() { return elem; }
public void setKey(Object k) { key = k; }
public void setElement(Object e) { elem = e; }
}
Comparators
- The most general and reusable form of a priority queue makes use of comparator objects. We don’t want to have to implement a different priority queue for every key type and every way of comparing them.
- Comparator objects are external to the keys that are to be compared and compare two objects. If we required keys to compare themselves, ambiguities could result. For example, numerical vs. lexicographical comparison.
- When the priority queue needs to compare two keys, it uses the comparator it is given to do the comparison.
- Thus any priority queue can be general enough to store any object.
- The Comparator ADT includes the following methods, all of which return boolean values:
- isLessThan(Object a, Object b)
- isLessThanOrEqualTo(Object a, Object b)
- isEqualTo(Object a, Object b)
- isGreaterThan(Object a, Object b)
- isGreaterThanOrEqualTo(Object a, Object b)
- isComparable(Object a)
- Let’s try to implement a priority queue with an unsorted sequence S.
- The element-items of S are a composition of two objects, the key k and the element e.
- We can implement insertItem() by using insertFirst() of the Sequence ADT. This would take O(1) time.
- However, because we always insertFirst() regardless of the key value, out sequence is unordered.
- Thus, for methods such as minElement(), minKey(), and removeMinElement(), we need to look at all elements of S. The worst-case time complexity for these methods is Q(n).
Implementation with a Sorted Sequence
- Another implementation uses a sequence S that is sorted by keys such that the first element of S has the smallest key.
- We can implement minElement(), minKey(), and removeMinElement() by accessing the first element of S. Thus, these methods are O(1), assuming our sequence has O(1) front-removal.
- However, these advantages come at a price. To implement insertItem(), we might now have to scan through the entire sequence. Thus inserItem() is O(n).
Cost of Operations
Sequence-Based Priority Queue
Sequence |
||
- A sorted-sequence implementation of the SimplePriorityQueue ADT.
public class SequenceSimplePriorityQueue implements SimplePriorityQueue {
//# Implementation of a priority queue using a sorted sequence
protected Sequence seq = new NodeSequence();
protected Comparator comp;
// auxiliary methods
protected Object extractKey (Position pos) {
return ((Item)pos.element()).key();
}
protected Object extractElem (Position pos) {
return ((Item)pos.element()).element();
}
protected Object extractElem (Item kep) {
return kep.element();
}
Class SequenceSimplePriorityQueue (cont.)
// methods of the SimplePriorityQueue ADT
public SequenceSimplePriorityQueue (Comparator c) {
this.comp = c;
} public int size () {return seq.size(); }
public boolean isEmpty () { return seq.isEmpty(); }
public void insertItem (Object k, Object e) throws InvalidKeyException {
if (!comp.isComparable(k))
throw new InvalidKeyException("The key is not valid");
else
if (seq.isEmpty())
seq.insertFirst(new Item(k,e));
else
if (comp.isGreaterThan(k,extractKey(seq.last())))
seq.insertAfter(seq.last(),new Item(k,e));
else {
Position curr = seq.first();
while (comp.isGreaterThan(k,extractKey(curr)))
curr = seq.after(curr);
seq.insertBefore(curr,new Item(k,e));
}
}
Class SequenceSimplePriorityQueue (cont.)
public Object minElement () throws EmptyContainerException {
if (seq.isEmpty())
throw new EmptyContainerException("The priority queue is empty");
else
return extractElem(seq.first());
}
// methods minKey and removeMinElement are not
// shown.
}
Selection Sort
- Selection Sort is a variation of PriorityQueueSort that uses an unsorted sequence to implement the priority queue P.
- Phase 1, the insertion of an item into P takes O(1) time.
- Phase 2, removing an item from P takes time proportional to the number of elements in P.
| Input | ||
| Phase 1:
(a)
(b)
…
(g)
|
{8,2,5,3,9} … {} |
{7,4} … {7,4,8,2,5,3,9} |
| Phase 2:
(a)
(b)
(c)
(d)
(e)
(f)
(g)
|
{2,3} {2,3,4} {2,3,4,5} {2,3,4,5,7} {2,3,4,5,7,8} {2,3,4,5,7,8,9} |
{7,4,8,5,9} {7,8,5,9} {7,8,9} {8,9} {9} {} |
- Clearly, a bottleneck exists in phase 2. The first call to removeMinElement takes Q(n), the second Q(n-1), etc., until the last removal takes Q(1) time.
- The total time needed for phase 2 is then
.-
Recall that
.
- The total time complexity of phase 2 is then Q(n2 ).
- Thus the total time complexity of the algorithm is
.
Insertion Sort
- Insertion sort is the sort that results when we perform a PriorityQueueSort implementing the priority queue with a sorted sequence.
- The cost of phase 2 is improved to O(n).
- However, phase 1 now becomes the bottleneck for the running time. The first insertItem takes O(1), the second O(2), until the last insertItem takes O(n).
- The run time of phase 1 is
.- The overall run time of the algorithm is
Insertion Sort (cont.)
| Input | ||
| Phase 1:
(a)
(b)
(c)
(d)
(e)
(f)
(g)
|
{8,2,5,3,9} {2,5,3,9} {5,3,9} {3,9} {9} {} |
|
| Phase 2:
(a)
(b)
…
(g)
|
{2,3} … {2,3,4,5,7,8,9} |
{4,5,7,8,9} … {} |
| Phase 1 | Phase 2 | Total | |||
| Selection Sort | O(n) | + | Q(n2 ) | = | Q(n2 ) |
| Insertion Sort | O(n2) | + | O(n) | = | O(n2 ) |
- Selection sort and insertion sort both take O(n2 ).
- Selection sort will always take W(n2 ) time, no matter what the input sequence.
- The cost of insertion sort varies depending on the input sequence.
- If we remove from the rear of an already sorted input sequence S or remove from the front of a reverse-ordered sequennce, then the (best-case) cost of phase 1 of insertion sort is O(n). Thus, nearly sorted sequences will perform better for insertion sort.
.
