Priority Queue (ADT)

Methods in an ADT:

• insert(k,x): inserts an entry with key $k$ and value $x$ into a priority key $P$.
• removeMin(): removes the entry with smallest key from $P$.
• min(): returns but does not remove an entry of $P$ with smallest key.
• size(): returns the number of entries in priority queue $P$.
• isEmpty(): tests whether priority queue $P$ is empty.

Entry ADT

An entry in a priority key is simply a key-value pair. There may be two methods: getKey(), getValue().

Comparator ADT

A comparator encapsulates the action of comparing two objects according to a given Total Order Relation.

The primary method of the comparator is:

• compare(x,y): returns an integer $i$ such that:
  • $i<0$ if $x<y$
  • $i=0$ if $x=y$
  • $i>0$ if $x>y$