Comparators

A Comparator is a software mechanism that defines how objects are ordered — it tells us whether A < B, A = B, or A > B.

• Must be consistent across all objects → this is called a total order relation.
• You can have different comparators for the same objects (e.g., order by name vs. age).
• A comparator can be passed into sorting algorithms.

# java.util package

public int compare(Object o1, Object o2)

Returns:

• negative → o1 < o2
• zero → o1 == o2
• positive → o1 > o2

The actual numeric value doesn’t matter (only the sign does).

Total Order Relation Properties

For all a, b, c in set S:

• (a ≤ b) ∨ (or) (b ≤ a) → comparability
• (a ≤ b) ∧ (and) (b ≤ a) ⇒ (a = b) → antisymmetry
• (a ≤ b) ∧ (and) (b ≤ c) ⇒ (a ≤ c) → transitivity

Priority Queue

A Priority Queue is like a queue, but each item has a priority. Only the “highest-priority” (lowest key) element can be removed first.