Priority Queue

Created

PriorityQueue ADT

A Priority Queue is a variation of a standard queue where the values come out in the order of highest priority.

  • The "priority" by default is based on the natural ordering of elements. If two priorities are the same, they are removed based on "first come, first serve/"

A binary heap enables us to efficiently implement PriorityQueue ADT.

ADT:

public interface PriorityQueue<T extends Comparable<T>> {
	void insert (T t);
	// removes the best value
	void remove() throws EmptyException;
	// returns the value with the greatest priority
	T best() throws EmptyException;
	boolean empty();
}

  • The elements must be Comparable.

  • By default,a PriorityQueue will order the elements based on their natural ordering.

    • natural ordering means the default ordering of objects of a specifc type when they are sorted in an array.
    • A class that implements the Comparable interface is said to have a natural ordering. compareTo() method is called the natural comparison methd.

  • Priorities are indicated by the natural ordering of elements (like smallest or largest), but we could also provide priorities separately:

public interface PriorityQueue(<P extends Comparable<P>,T>) {
	void insert(P p, T t);
}

In this case, the priorities are associated with values just like how "keys" are associated with values in an ordered dictionary. Only P needs to be comparable.

  • Prioriy queue is a "restricted access" data structure.
  • best can be defined to return the largest or smallest value.
  • Duplicate values are allowed.

Implementation

Suppose we want a LinkedList or Array implementation. Its core operations consist of:

  • If the underlying data is sorted, remove and best will be in constant time. However, insert will be O(n) time becuse you must shift elements around. A linked list implemnetation will require a linear search to find where to insert.
  • If the underlying data is unsorted, we must perform a linear seaerch for finding/removing best.

Tree Implementation

A tree-based implementation of PriorityQueue is called a Binary Heap. It's a binary tree where it is structured by the following properties:

  • Structure (shape) property: a heap is a complete tree.
    • Implies the height of the tree is O(lgn).
  • Order (heap) property: the element stored at each node has a higher priority (considered "better") then its children.
    • Implies the "best" element is always at the root.

A complete binary tree is one where the tree is "full" on all levels except possiblythe last, and the last level has all its node on the left side.

  • A perfect binary tree is one that has all its levels full.

Heap Order Property

The min-heap property: the value of each nodes is less than or equal to the value of its The max-heap property: the value of each nodes is greater than or equal to the value of its children with the minimum-value element at the root. Best = largest.

The max-heap property: the value of each nodes is greater than or equal to the value of its children with the maximum-value element at the root. Best = largest.

Ranked Array Representation

A complete binary tree can be unique represented by storing its level order traversal in an array.

  • The root will be the second item in the array (index = 1).
  • Consider the kth element of the array
    • It's left child is located at 2*k index
    • its right child is located at 2*k+1 index
    • its parent is located at k/2 index.

Best Operation

"best" element is always at the root of the binary heap implementation and runs with O(n) time.

Insert Operation

To insert, appen it to the end o the heap (last level, furthest to the left).

Then, "repair" the heap property by percolating the new node to its proper position. Swim-up involves comparing the added element with its parent and moving it up a level (swap) if needed.

The comparison is repeated until the parent is smaller than or equal to the percolating (swimming) element.

The worst-case runtime of the algorithm is O(lgn), since we need at most one swap on each level of a heap on the path from the inserted node to the root.

Remove operation

To remove the best, replace root with the last element of the heap (to preserve complete binary tree) and delete the last element.

Restore the heap property by percolating the new root down. This is called sink-down and it involves comparing the added elemenet with its children and moving it down a level (swap with smaller of the two children) if needed.

This process is repeated until the children are smaller than or equal to the percolating (sinking) element or until the percolating (sinking) reaches thedeapest level.

Runtime is O(lgn) since we need at most one swap on each heap level on the path from the root node to the deepest level.

PQ Constructors

An implementation of PriorityQueue must provide two consturctors: a default constructor (with no arguments) and a non-default one which allows a Comparator to be provided to overwrite the natural ordering of the element types.

public class BinaryHeapPriorityQueu<T extends Comparable<T>> implements PriorityQueue<T> {
	private Comparator<T> cmp; 
	public BinaryHeapPriorityQueue() {
		this(new DefaultComparator<>());
	}
	
	public BinaryHeapPriorityQueue(Comparator<T> cmp) {
	this.cmp cmp;
	// TODO
	}
	
	// the default comparator uses "natural" odering
	private static class DefaultComparator<T extends Comparable<T>> implements Comparator<T> {
		public int compare(T t1, T t2) {
			return t1.compareTo(t2);
		}
	}
}

Notice the sue of Comparator<T>, an interface that defines a compare(T o1, T o2) method with two arguments thar represents compared objects.

Comparable vs Comparator

Comparable has a method named compareTo. Comparator has a method named compare(T t1, T t2.

If a type were comparable, it would implement Comparable

Example: Say we have a Submission class that represents a homework submission made by a student and has the following attributes:

private int positionInQueue;
private String student;
private int numPriorSubmission;

The submissions are comparable to another.

@override
public int compareTo (Submission other) {
	return this.positionInQueue - other.positionInQueue;
}
  • Since this class implements the Comparable interface, it is said to have a natural ordering. compareTo() above is called the natural comparison method.
  • Grading the submissions in the order that they came in would be a first-in-first-out situation so a queue is the most suitable data structure

If we want to prioritize the grading of submission by the number of prior submissions by the students, we would need to overwrite the natural ordering of Submission objects. Do this by providing a Comparator to Collections.sort.

Collections.sort(submissions, new LessSubmissionHigherPriortiy());

where LessSubmissionHigherPriortiy is defined:

private static class LessSubmissionHigherPriortiy implements Comparator<Submission> {
	@Overrie
	public int compare (Submission s1, Submission s2,) {
		return s1.getNumPriorSubmission() - s2.getNumPriorSubmission(); 
	}
}
  • Java's Comparator<T> interface defined a compare(T o1, T o2) method that works similar to the Comparable.compareTo() method.

Linked from Data Structures