2025 Paper 1 Question 3 — PriorityQueue, Comparable/Comparator, and Observer Pattern

Question

The Java Collections framework contains PriorityQueue<E>, which represents a priority queue based on a priority heap of objects of type E. Priority is specified implicitly by providing an ordering on E via either the Comparable or Comparator interfaces. Consider a task tracking app that uses the following class to represent a task:

public class WorkTask {
    private int priority;
    private String description;
    public WorkTask(String descriptor, int priority) {
        this.descriptor = descriptor;
        this.priority = priority;
    }
    public int getPriority() { return priority; }
    public int setPriority(int priority) { this.priority = priority; }
}

(a)

• (i) Compare and contrast Comparable and Comparator in Java’s Collections framework. [3 marks]
• (ii) Show how to make a PriorityQueue<WorkTask> maintain its contents highest priority first using:
  • (A) Comparable [2 marks]
  • (B) Comparator [2 marks]
• (iii) Would you prefer Comparable or Comparator for this application? Explain your answer. [1 mark]

(b) PriorityQueue does not offer a method to change priorities. Instead, an object with a changed priority must be removed and reinserted. Using a design pattern that you should specify, write code for AutoUpdatableQueue, which extends PriorityQueue and automatically updates the queue when the priority of any object in the queue is updated. Make your solution flexible and demonstrate how to apply it to a queue of WorkTasks. [12 marks]

---

Worked Solution

(a)(i) Comparable vs Comparator — 3 marks

Model answer:

Aspect	Comparable<T>	Comparator<T>
Package	java.lang	java.util
Method	int compareTo(T other)	int compare(T a, T b)
Where defined	On the class being compared	In a separate class
Number of orderings	One (natural ordering)	Many (different comparators for different sort orders)
Modifies the class?	Yes — the class implements Comparable	No — external to the class

Key differences:

• Comparable defines the natural ordering — the class itself declares “this is how you compare me.” Example: String implements Comparable<String> (lexicographic order). Every String knows how to compare itself to another String.
• Comparator defines an external ordering — a separate object that knows how to compare two instances. Example: Collections.sort(list, Comparator.comparing(String::length)) sorts by a criterion the String class does not define itself.

When to use each:

• Use Comparable when there is one obvious, natural ordering for the class (e.g., Integer, LocalDate).
• Use Comparator when you need multiple orderings (sort employees by name, by salary, by hire date), when you cannot modify the class, or when the ordering is context-dependent.

Why 3 marks: Explain both interfaces with their method signatures, describe the “one ordering vs many orderings” distinction, and give appropriate use cases.

(a)(ii)(A) Using Comparable — 2 marks

Model answer: WorkTask implements Comparable<WorkTask>, defining its natural ordering by priority (highest priority first):

public class WorkTask implements Comparable<WorkTask> {
    private int priority;
    private String description;

    public WorkTask(String description, int priority) {
        this.description = description;
        this.priority = priority;
    }

    public int getPriority() { return priority; }
    public void setPriority(int priority) { this.priority = priority; }

    @Override
    public int compareTo(WorkTask other) {
        return Integer.compare(other.priority, this.priority);
    }
}

// Usage
PriorityQueue<WorkTask> queue = new PriorityQueue<>();
queue.add(new WorkTask("Fix bug", 5));
queue.add(new WorkTask("Write docs", 3));
// Highest priority (5) comes out first

Note: Integer.compare(other.priority, this.priority) compares other first — this is reversed from the natural Integer.compare(this.priority, other.priority). Because we want highest priority first, a task with priority 5 should be less than a task with priority 3 in the queue ordering (since PriorityQueue’s head is the smallest element).

Actually, let me verify: PriorityQueue orders by natural ordering (smallest first). To get highest priority first:

• compareTo should return negative when this has higher priority (should come out first).
• So: Integer.compare(other.priority, this.priority) — if this.priority = 5 and other.priority = 3, compare(3, 5) returns negative, meaning this (priority 5) is “smaller” and comes out first. Correct.

Alternatively: return -(Integer.compare(this.priority, other.priority)).

(a)(ii)(B) Using Comparator — 2 marks

Model answer: Create a Comparator<WorkTask> that orders by highest priority first, and pass it to the PriorityQueue constructor:

Comparator<WorkTask> highestPriorityFirst = (a, b) ->
    Integer.compare(b.getPriority(), a.getPriority());

PriorityQueue<WorkTask> queue = new PriorityQueue<>(highestPriorityFirst);
queue.add(new WorkTask("Fix bug", 5));
queue.add(new WorkTask("Write docs", 3));
// Highest priority (5) comes out first

Or using Comparator.comparingInt:

PriorityQueue<WorkTask> queue = new PriorityQueue<>(
    Comparator.comparingInt(WorkTask::getPriority).reversed()
);

Why 2 marks for each: Correct implementation of the ordering (highest priority first), correct use of the PriorityQueue API, and correct syntax for whichever approach is used.

(a)(iii) Prefer Comparable or Comparator? — 1 mark

Model answer: Comparator is preferred.

Reasoning: Task priority is not an intrinsic property of a task’s identity — it is a scheduling concern that might vary by context. One part of the application might sort tasks by priority, another by deadline, another by assignee. Implementing Comparable hard-codes one ordering, but tasks need multiple orderings. Using Comparator lets different parts of the application create PriorityQueue instances with the ordering appropriate to their context, without polluting the WorkTask class.

Additionally: The question statement that “priority is specified implicitly by providing an ordering on E” and part (a)(ii) asks for both approaches — but the preferred approach for any domain object that may be sorted differently in different contexts is Comparator.

(b) AutoUpdatableQueue — 12 marks

Model answer: Using the Observer pattern combined with the Decorator pattern (or a wrapper/adapter approach). The AutoUpdatableQueue wraps a PriorityQueue and observes the elements within it. When an element’s priority changes, the queue detects the change and reorders itself.

Alternative perspective: This is the Observer pattern — the queue is an observer of the tasks, and tasks are subjects that notify the queue when their priority changes.

import java.util.*;

interface PriorityObservable {
    int getPriority();
    void addPriorityListener(PriorityListener listener);
    void removePriorityListener(PriorityListener listener);
}

interface PriorityListener {
    void onPriorityChanged(PriorityObservable source);
}

class ObservableWorkTask implements PriorityObservable {
    private final String description;
    private int priority;
    private final List<PriorityListener> listeners = new ArrayList<>();

    ObservableWorkTask(String description, int priority) {
        this.description = description;
        this.priority = priority;
    }

    String getDescription() { return description; }

    @Override
    public int getPriority() { return priority; }

    public void setPriority(int newPriority) {
        this.priority = newPriority;
        notifyListeners();
    }

    @Override
    public void addPriorityListener(PriorityListener listener) {
        listeners.add(listener);
    }

    @Override
    public void removePriorityListener(PriorityListener listener) {
        listeners.remove(listener);
    }

    private void notifyListeners() {
        for (PriorityListener l : listeners) {
            l.onPriorityChanged(this);
        }
    }
}

class AutoUpdatableQueue extends PriorityQueue<ObservableWorkTask>
        implements PriorityListener {

    private final Comparator<ObservableWorkTask> comparator;

    AutoUpdatableQueue(Comparator<ObservableWorkTask> comparator) {
        super(comparator);
        this.comparator = comparator;
    }

    @Override
    public boolean add(ObservableWorkTask task) {
        task.addPriorityListener(this);
        return super.add(task);
    }

    @Override
    public boolean remove(Object o) {
        if (o instanceof ObservableWorkTask) {
            ((ObservableWorkTask) o).removePriorityListener(this);
        }
        return super.remove(o);
    }

    @Override
    public void onPriorityChanged(PriorityObservable source) {
        if (source instanceof ObservableWorkTask) {
            ObservableWorkTask task = (ObservableWorkTask) source;
            remove(task);
            add(task);
        }
    }
}

Demonstration with WorkTasks:

Comparator<ObservableWorkTask> highestFirst =
    (a, b) -> Integer.compare(b.getPriority(), a.getPriority());

AutoUpdatableQueue queue = new AutoUpdatableQueue(highestFirst);

ObservableWorkTask task1 = new ObservableWorkTask("Fix bug", 5);
ObservableWorkTask task2 = new ObservableWorkTask("Write docs", 3);
ObservableWorkTask task3 = new ObservableWorkTask("Refactor code", 7);

queue.add(task1);
queue.add(task2);
queue.add(task3);

System.out.println(queue.peek().getDescription()); // Refactor code (priority 7)

task2.setPriority(10);  // "Write docs" now has priority 10
System.out.println(queue.peek().getDescription()); // Write docs (now priority 10)

task1.setPriority(1);   // "Fix bug" now has priority 1
System.out.println(queue.peek().getDescription()); // Write docs (still priority 10)

Why this design works (for the 12 marks):

1. Observer pattern — The queue is a PriorityListener. When a task’s priority changes, the task notifies the queue via onPriorityChanged(). The queue then removes and re-adds the task, forcing the heap to reorder.

2. Loose coupling — The queue depends only on the PriorityObservable and PriorityListener interfaces, not on the concrete ObservableWorkTask class. The solution works with any PriorityObservable.

3. Correct heap reordering — PriorityQueue’s heap structure is not automatically maintained when elements’ priorities change. The remove-then-add pattern forces the element to be re-heapified correctly. This is $O(\log n)$ per update (remove + add), which is efficient.

4. Extends PriorityQueue — As required, AutoUpdatableQueue extends PriorityQueue. It inherits all standard PriorityQueue behaviour and adds the auto-update capability.

5. Flexibility — The Comparator is passed through the constructor, so the queue can be used with any ordering. The element type is ObservableWorkTask but could be made generic (AutoUpdatableQueue<E extends PriorityObservable>).

Alternative (more flexible, generic version):

class AutoUpdatableQueue<E extends PriorityObservable> extends PriorityQueue<E>
        implements PriorityListener {

    AutoUpdatableQueue(Comparator<E> comparator) {
        super(comparator);
    }

    @Override
    public boolean add(E task) {
        task.addPriorityListener(this);
        return super.add(task);
    }

    @Override
    public boolean remove(Object o) {
        if (o instanceof PriorityObservable) {
            ((PriorityObservable) o).removePriorityListener(this);
        }
        return super.remove(o);
    }

    @Override
    public void onPriorityChanged(PriorityObservable source) {
        @SuppressWarnings("unchecked")
        E task = (E) source;
        remove(task);
        add(task);
    }
}

Key design decisions and tradeoffs:

1. Observer vs polling — The Observer approach means the queue reactively updates when priorities change, with no CPU wasted on polling. The tradeoff is that tasks must be modified to support the Observer contract (they need the PriorityObservable interface).

2. Thread safety — This implementation is not thread-safe. If multiple threads modify task priorities concurrently, the heap could become corrupted. A thread-safe version would synchronise onPriorityChanged or use a concurrent queue.

3. Listener management — Adding a listener on add() and removing on remove() ensures the queue does not hold stale references to removed tasks (preventing memory leaks). If you also poll tasks (which calls remove), the listener is properly cleaned up.

4. Circular notification — Be careful: when the queue re-adds the task in onPriorityChanged, it calls add() again, which re-registers the listener. This is harmless (duplicate registration), but could be optimised by checking if the listener is already registered.

Why 12 marks: This is the highest-mark part on any of these papers. The solution must: (a) name the pattern (Observer), (b) design the interfaces (PriorityObservable, PriorityListener), (c) implement the concrete observable task class, (d) implement AutoUpdatableQueue extending PriorityQueue, (e) demonstrate it working with WorkTasks, (f) discuss design decisions and tradeoffs. The flexibility of the solution (working with any observable type, any comparator) is key to the high marks.