Java PriorityQueue: ordered removal without a sorted list

Priority is a removal rule

A queue of support tickets needs to pick the highest urgency first, with an older sequence number breaking ties. Define that comparator once. The program treats a smaller urgency value as more urgent and then compares the sequence.

The tie-breaker matters. Equal comparator results do not give a stable arrival-order guarantee. If FIFO ordering within a priority group is required, include a monotonic sequence and consider what happens when its range is exhausted.

Use Integer.compare, Long.compare, or comparator helpers instead of subtracting values. Subtraction can overflow and reverse an ordering decision at the edges of the numeric range.

Read through poll

poll removes the current head. Repeating it produces the comparator’s removal order. A for-each loop, toString, or iterator over the queue does not promise that order.

The queue holds references. Changing a ticket’s priority after inserting it does not automatically repair its heap position. Keep ordering fields immutable, or remove and reinsert an updated ticket.

PriorityQueue rejects null elements and is not a blocking concurrent handoff mechanism. A task scheduler may need a worker service, bounded admission, cancellation, and a clear shutdown policy in addition to selecting the next item.

Working program

import java.util.Comparator;
import java.util.PriorityQueue;

public class SupportTicketQueue {
    static final class Ticket {
        final int urgency;
        final long sequence;
        final String id;
        Ticket(int urgency, long sequence, String id) {
            this.urgency = urgency;
            this.sequence = sequence;
            this.id = id;
        }
    }
    public static void main(String[] args) {
        Comparator<Ticket> order = Comparator.comparingInt((Ticket ticket) -> ticket.urgency)
                .thenComparingLong(ticket -> ticket.sequence);
        PriorityQueue<Ticket> tickets = new PriorityQueue<>(order);
        tickets.add(new Ticket(2, 1, "billing-17"));
        tickets.add(new Ticket(1, 2, "login-42"));
        tickets.add(new Ticket(1, 3, "login-43"));
        while (!tickets.isEmpty()) {
            System.out.println(tickets.poll().id);
        }
    }
}

Output

login-42
login-43
billing-17

Cost and design choices

Inserting and polling an element take O(log n) heap work for n elements, excluding comparator cost. Peeking at the head is O(1). Searching for a particular arbitrary element still requires O(n) work.

Each ticket is stored once, so the queue occupies O(n) element-reference storage. A stream of tickets arriving faster than they are processed will keep growing unless admission is bounded elsewhere.

For processing an entire immutable batch in sorted order, sorting the batch once may be easier to reason about. A priority queue fits repeated insertion mixed with next-item removal.

Common Mistakes

• Do not expect iterator order to be priority order.
• Do not mutate comparator fields while an element is queued.
• Do not use arithmetic subtraction as a comparator.

Continue with collection and web contracts

Continue with Java PriorityQueue: define tie order in the comparator.