How to Use PriorityQueue and TreeMap in Java (Java 21)

Tickets in, work order out

Six support tickets go in, in whatever order they arrived. This is what comes out when you ask the desk what to work on:

Work order:
  #2 URGENT (open@5, due@30) Payments page 500s
  #6 URGENT (open@5, due@30) Export hangs at 90%
  #5 HIGH (open@3, due@120) Login fails on Safari
  #4 HIGH (open@9, due@120) Invoice PDF is blank
  #1 NORMAL (open@0, due@240) Password reset loop
  #3 LOW (open@7, due@1440) Typo on pricing page
Breached by minute 60:
  #2 URGENT (open@5, due@30) Payments page 500s
  #6 URGENT (open@5, due@30) Export hangs at 90%
Next deadline after 30: 120

Two collections do all of that. A PriorityQueue answers "what's next?" and a TreeMap answers "what's due between here and there?". If you've ever sorted a list on every request only to read its first element, this article is for you. By the end you'll know how to use PriorityQueue and TreeMap in Java well enough to pick the right one, and you'll have watched seven different things go wrong on purpose.

The whole project is five small classes and no dependencies. Writing it was quick. Breaking it on purpose took longer, and most of that time went on trap 5, because the map doesn't complain when it loses your data.

Both collections order things with a comparator. If Comparable and Comparator still feel fuzzy, read how to implement Comparable and Comparator in Java first. It's ten minutes and everything below leans on it.

Toolchain for this one

Any JDK from 17 up works. I compiled the main sources again with --release 17 and nothing changed, because records are the newest feature used. No Maven or Gradle, no test framework: the checks are a small main method, so there's nothing to download. If you want JUnit instead, how to write unit tests with JUnit 5 is where that lives.

You should already be comfortable with records and enums. The ticket is a record and the priority is an enum; how to use Java records and how to use Java enums with fields and methods cover both.

Set up the help-desk project from scratch

From any empty folder:

mkdir -p helpdesk/src/desk && cd helpdesk

The layout, once you've written the files below:

helpdesk/
└── src/desk/
    ├── Priority.java
    ├── Ticket.java
    ├── TicketQueue.java
    ├── SlaBoard.java
    ├── Main.java
    ├── Checks.java
    └── Traps.java

Every class lives in the package desk, so every file starts with package desk; and sits in src/desk/.

In IntelliJ IDEA

Verified from docs, not executed. Choose New Project, pick Java, set the build system to IntelliJ, and select a JDK 21. Create the package desk under src and add the classes there. Run Main with the gutter's green arrow.

In Eclipse

Verified from docs, not executed. File → New → Java Project, JRE set to 21, then right-click src → New → Package named desk. Run Main with Run As → Java Application.

How to use PriorityQueue and TreeMap in Java, step by step

Step 1: Write the priority enum

Goal: give priorities a sort order without writing any comparison code.

src/desk/Priority.java

package desk;

public enum Priority {
    URGENT, HIGH, NORMAL, LOW   // declaration order is the sort order: URGENT sorts first
}

An enum's natural order is its declaration order, so URGENT compares as smaller than LOW. Reorder the constants and you've reordered the queue. I'd rather have that in one visible place than hidden in a switch.

Step 2: Write the ticket and its work-order comparator

Goal: define "which ticket comes first" once, and make it a total order.

src/desk/Ticket.java

package desk;

import java.util.Comparator;

public record Ticket(int id, String title, Priority priority, int openedAt, int dueAt) {

    public Ticket {
        if (title == null || title.isBlank()) throw new IllegalArgumentException("title is required");
        if (priority == null) throw new IllegalArgumentException("priority is required");
        if (dueAt < openedAt) throw new IllegalArgumentException("dueAt is before openedAt");
    }

    /** Most urgent first, then oldest first, then lowest id. The id makes the order total. */
    public static final Comparator<Ticket> WORK_ORDER =
            Comparator.comparing(Ticket::priority)
                      .thenComparingInt(Ticket::openedAt)
                      .thenComparingInt(Ticket::id);

    public Ticket withPriority(Priority p) {
        return new Ticket(id, title, p, openedAt, dueAt);
    }

    @Override public String toString() {
        return "#" + id + " " + priority + " (open@" + openedAt + ", due@" + dueAt + ") " + title;
    }
}

The comparator has three keys: priority, then the minute the ticket opened (older first), then the id. The id is the tiebreaker that makes the order total, so two different tickets never compare as equal. That matters for the queue (it keeps output stable between runs) and it matters a great deal for the map in Step 4.

Checkpoint: compile what you have.

javac -d out src/desk/Priority.java src/desk/Ticket.java

No output means it worked.

Step 3: Write the queue wrapper around PriorityQueue

Goal: expose only what the desk needs, and hide the parts of PriorityQueue that mislead.

src/desk/TicketQueue.java

package desk;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class TicketQueue {

    private final PriorityQueue<Ticket> heap = new PriorityQueue<>(Ticket.WORK_ORDER);

    public void add(Ticket t) { heap.add(t); }

    /** Removes and returns the ticket to work on next, or null when the queue is empty. */
    public Ticket next() { return heap.poll(); }

    public Ticket peek() { return heap.peek(); }

    public int size() { return heap.size(); }

    /** Changing a priority means remove + add. Never mutate a ticket that is already inside. */
    public boolean reprioritise(int id, Priority p) {
        for (Ticket t : heap) {
            if (t.id() == id) {
                heap.remove(t);                 // O(n) search, O(log n) fix-up
                heap.add(t.withPriority(p));
                return true;
            }
        }
        return false;
    }

    /** A sorted view for display. Iterating the heap directly is NOT sorted. */
    public List<Ticket> inWorkOrder() {
        PriorityQueue<Ticket> copy = new PriorityQueue<>(heap);   // copy keeps the comparator
        List<Ticket> out = new ArrayList<>(copy.size());
        while (!copy.isEmpty()) out.add(copy.poll());
        return out;
    }

    /** What the raw iterator gives you. Only here to show the trap. */
    public List<Ticket> rawIterationOrder() { return new ArrayList<>(heap); }
}

PriorityQueue is a binary heap. add and poll cost O(log n), peek is O(1), and remove(Object) is O(n) because it has to find the element first. That last one is why reprioritise is a remove followed by an add, never a field change on the ticket already inside. The record's withPriority returns a new ticket, so mutation isn't even possible, which is the point of using a record here.

inWorkOrder() drains a copy. The copy constructor that takes another PriorityQueue keeps the comparator; if you'd passed it a plain List you'd have lost it and gotten natural ordering, which for a Ticket means a ClassCastException.

Step 4: Write the SLA board on top of TreeMap

Goal: answer range and neighbour questions about deadlines without scanning.

src/desk/SlaBoard.java

package desk;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

/** Tickets indexed by the minute their SLA runs out. */
public class SlaBoard {

    private final TreeMap<Integer, List<Ticket>> byDue = new TreeMap<>();

    public void add(Ticket t) {
        byDue.computeIfAbsent(t.dueAt(), k -> new ArrayList<>()).add(t);
    }

    /** Everything already breached or breaching at 'now' (due at or before now). */
    public List<Ticket> breachedBy(int now) {
        return flatten(byDue.headMap(now, true));
    }

    /** Tickets due inside [from, to). */
    public List<Ticket> dueBetween(int from, int to) {
        return flatten(byDue.subMap(from, true, to, false));
    }

    /** The next deadline strictly after 'now', or null. */
    public Integer nextDeadlineAfter(int now) {
        return byDue.higherKey(now);
    }

    /** The most recent deadline at or before 'now', or null. */
    public Integer lastDeadlineAtOrBefore(int now) {
        return byDue.floorKey(now);
    }

    /** Takes the most urgent deadline off the board. */
    public List<Ticket> popEarliest() {
        Map.Entry<Integer, List<Ticket>> e = byDue.pollFirstEntry();
        return e == null ? List.of() : e.getValue();
    }

    public List<Ticket> latestFirst() {
        return flatten(byDue.descendingMap());
    }

    public int deadlineCount() { return byDue.size(); }

    private static List<Ticket> flatten(NavigableMap<Integer, List<Ticket>> view) {
        List<Ticket> out = new ArrayList<>();
        view.values().forEach(out::addAll);
        return out;
    }
}

A TreeMap keeps its keys sorted at all times (it's a red-black tree), and get, put and remove are O(log n). The reason to reach for it over a HashMap is the navigation methods: headMap for "up to here", subMap for "between these two", higherKey and floorKey for "the nearest one on either side".

Two things I want you to notice. The key is the due minute, not the ticket, so two tickets due at minute 30 share one bucket (a List). And the headMap(now, true) call takes an inclusive flag; the one-argument headMap(now) is exclusive and would miss a ticket due exactly now. People forget that flag, so there's a check for it.

Step 5: Write Main

Goal: drive both collections with the same six tickets.

src/desk/Main.java

package desk;

import java.util.List;

public class Main {
    static List<Ticket> sample() {
        return List.of(
            new Ticket(1, "Password reset loop",     Priority.NORMAL, 0,  240),
            new Ticket(2, "Payments page 500s",      Priority.URGENT, 5,   30),
            new Ticket(3, "Typo on pricing page",    Priority.LOW,    7, 1440),
            new Ticket(4, "Invoice PDF is blank",    Priority.HIGH,   9,  120),
            new Ticket(5, "Login fails on Safari",   Priority.HIGH,   3,  120),
            new Ticket(6, "Export hangs at 90%",     Priority.URGENT, 5,   30));
    }

    public static void main(String[] args) {
        TicketQueue queue = new TicketQueue();
        SlaBoard board = new SlaBoard();
        for (Ticket t : sample()) { queue.add(t); board.add(t); }

        System.out.println("Raw heap order (NOT sorted):");
        queue.rawIterationOrder().forEach(t -> System.out.println("  " + t));

        System.out.println("Work order:");
        queue.inWorkOrder().forEach(t -> System.out.println("  " + t));

        System.out.println("Peek: " + queue.peek());
        queue.reprioritise(3, Priority.URGENT);
        System.out.println("After escalating #3, next up: " + queue.next());

        System.out.println("Breached by minute 60:");
        board.breachedBy(60).forEach(t -> System.out.println("  " + t));
        System.out.println("Due in [100, 300): " + board.dueBetween(100, 300).stream().map(Ticket::id).toList());
        System.out.println("Next deadline after 30: " + board.nextDeadlineAfter(30));
        System.out.println("Last deadline at/before 119: " + board.lastDeadlineAtOrBefore(119));
        System.out.println("Latest first: " + board.latestFirst().stream().map(Ticket::id).toList());
        System.out.println("Pop earliest: " + board.popEarliest().stream().map(Ticket::id).toList()
                + ", deadlines left: " + board.deadlineCount());
    }
}

Compile everything and run it:

javac -Xlint:all -d out src/desk/*.java
java -cp out desk.Main

Windows (cmd or PowerShell) is the same command; use src\desk\*.java if the forward slashes give you trouble.

Run the desk

This is the complete output from my run.

Raw heap order (NOT sorted):
  #2 URGENT (open@5, due@30) Payments page 500s
  #5 HIGH (open@3, due@120) Login fails on Safari
  #6 URGENT (open@5, due@30) Export hangs at 90%
  #1 NORMAL (open@0, due@240) Password reset loop
  #4 HIGH (open@9, due@120) Invoice PDF is blank
  #3 LOW (open@7, due@1440) Typo on pricing page
Work order:
  #2 URGENT (open@5, due@30) Payments page 500s
  #6 URGENT (open@5, due@30) Export hangs at 90%
  #5 HIGH (open@3, due@120) Login fails on Safari
  #4 HIGH (open@9, due@120) Invoice PDF is blank
  #1 NORMAL (open@0, due@240) Password reset loop
  #3 LOW (open@7, due@1440) Typo on pricing page
Peek: #2 URGENT (open@5, due@30) Payments page 500s
After escalating #3, next up: #2 URGENT (open@5, due@30) Payments page 500s
Breached by minute 60:
  #2 URGENT (open@5, due@30) Payments page 500s
  #6 URGENT (open@5, due@30) Export hangs at 90%
Due in [100, 300): [4, 5, 1]
Next deadline after 30: 120
Last deadline at/before 119: 30
Latest first: [3, 1, 4, 5, 2, 6]
Pop earliest: [2, 6], deadlines left: 3

Read three lines closely. The first block, "Raw heap order", is what you get when you iterate the queue directly: the first element is right, and the rest is the heap's internal layout. The "Work order" block is the same data drained properly. And "After escalating #3, next up" is still ticket #2: ticket #3 became URGENT, but it opened at minute 7 and #2 opened at minute 5, so #2 stays ahead. If you expected #3 to jump the line, that's the age tiebreaker doing its job.

Pin the behaviour down with checks

A real project would use JUnit here. I kept to a plain main so the article runs on a bare JDK; each check prints PASS or FAIL and the process exits non-zero on any failure.

src/desk/Checks.java

package desk;

import java.util.List;

public class Checks {
    static int passed, failed;

    static void check(String name, boolean ok) {
        if (ok) passed++; else failed++;
        System.out.println((ok ? "PASS " : "FAIL ") + name);
    }

    static List<Integer> ids(List<Ticket> ts) { return ts.stream().map(Ticket::id).toList(); }

    public static void main(String[] args) {
        TicketQueue q = new TicketQueue();
        SlaBoard b = new SlaBoard();
        for (Ticket t : Main.sample()) { q.add(t); b.add(t); }

        check("work order is priority, then age, then id", ids(q.inWorkOrder()).equals(List.of(2, 6, 5, 4, 1, 3)));
        check("inWorkOrder does not drain the queue", q.size() == 6);
        check("raw iteration is not the work order", !ids(q.rawIterationOrder()).equals(List.of(2, 6, 5, 4, 1, 3)));
        check("peek does not remove", q.peek().id() == 2 && q.size() == 6);
        check("next removes in order", q.next().id() == 2 && q.next().id() == 6 && q.size() == 4);

        check("reprioritise finds the ticket", q.reprioritise(3, Priority.URGENT));
        check("escalated ticket jumps the line", q.next().id() == 3);
        check("reprioritise unknown id is false", !q.reprioritise(99, Priority.LOW));
        check("empty queue returns null", new TicketQueue().next() == null);

        check("breachedBy is inclusive", ids(b.breachedBy(30)).equals(List.of(2, 6)));
        check("breachedBy before first deadline is empty", b.breachedBy(29).isEmpty());
        check("dueBetween includes from, excludes to", ids(b.dueBetween(30, 120)).equals(List.of(2, 6)));
        check("nextDeadlineAfter is strict", b.nextDeadlineAfter(30) == 120);
        check("nextDeadlineAfter past the end is null", b.nextDeadlineAfter(1440) == null);
        check("lastDeadlineAtOrBefore is inclusive", b.lastDeadlineAtOrBefore(120) == 120);
        check("lastDeadlineAtOrBefore before first is null", b.lastDeadlineAtOrBefore(10) == null);
        check("same-deadline tickets share one key", b.deadlineCount() == 4);
        check("latestFirst reverses deadline order", ids(b.latestFirst()).equals(List.of(3, 1, 4, 5, 2, 6)));
        check("popEarliest returns both tickets", ids(b.popEarliest()).equals(List.of(2, 6)) && b.deadlineCount() == 3);

        boolean threw = false;
        try { new Ticket(1, " ", Priority.LOW, 0, 1); } catch (IllegalArgumentException e) { threw = true; }
        check("blank title rejected", threw);

        System.out.println(passed + " passed, " + failed + " failed");
        if (failed > 0) System.exit(1);
    }
}

java -cp out desk.Checks

PASS work order is priority, then age, then id
PASS inWorkOrder does not drain the queue
PASS raw iteration is not the work order
PASS peek does not remove
PASS next removes in order
PASS reprioritise finds the ticket
PASS escalated ticket jumps the line
PASS reprioritise unknown id is false
PASS empty queue returns null
PASS breachedBy is inclusive
PASS breachedBy before first deadline is empty
PASS dueBetween includes from, excludes to
PASS nextDeadlineAfter is strict
PASS nextDeadlineAfter past the end is null
PASS lastDeadlineAtOrBefore is inclusive
PASS lastDeadlineAtOrBefore before first is null
PASS same-deadline tickets share one key
PASS latestFirst reverses deadline order
PASS popEarliest returns both tickets
PASS blank title rejected
20 passed, 0 failed

To prove the checks can fail, I deleted the thenComparingInt(Ticket::openedAt) line from the comparator and recompiled. The result:

FAIL work order is priority, then age, then id
19 passed, 1 failed

Only the first check caught it, which tells me the age rule is covered once and not twice. Good enough for a tutorial; add more cases if this were going to production.

Why a heap sorts only one end

A binary heap guarantees one thing: the smallest element is at the front. Every parent is no larger than its children, and that's all. It says nothing about siblings, so the array behind the queue looks scrambled even though poll always returns the right element next. Sorting the whole thing on every insert would cost O(n log n); the heap pays O(log n) and promises less. That trade is the reason to use it. When you only ever need the next item, you shouldn't pay to know the order of the rest.

A TreeMap makes the opposite trade. It keeps everything sorted, pays O(log n) on writes, and in return it can answer questions about any position, not only the front. Use the queue when you consume from one end; use the map when you ask "what's near this value?".

TreeMap decides whether two keys are the same by calling the comparator, not equals. Trap 5 below shows what that does when the comparator is too coarse.

For the concurrent versions, PriorityBlockingQueue and ConcurrentSkipListMap exist because neither class here is thread-safe. The producer-consumer side is in how to use BlockingQueue for producer-consumer pipelines, and how to use ConcurrentHashMap covers the unsorted map.

Seven traps, each one forced

I wrote Traps.java to trigger each of these. It's one file; the output below is from my run.

src/desk/Traps.java

package desk;

import java.util.*;

public class Traps {
    static class Plain { }                       // not Comparable
    static final class Mutable { int rank; Mutable(int r) { rank = r; } public String toString() { return "r" + rank; } }

    public static void main(String[] args) {
        System.out.println("-- 1. toString of a PriorityQueue");
        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4, 2, 3));
        System.out.println(pq + "  <- not sorted");

        System.out.println("-- 2. no Comparator, not Comparable");
        try { new PriorityQueue<Plain>().add(new Plain()); }
        catch (ClassCastException e) { System.out.println(e.getClass().getSimpleName() + ": " + e.getMessage().replaceAll("desk\\.", "")); }

        System.out.println("-- 3. null element / null key");
        try { new PriorityQueue<Ticket>().add(null); } catch (NullPointerException e) { System.out.println("PriorityQueue.add(null): NullPointerException"); }
        try { new TreeMap<Integer, String>().put(null, "x"); } catch (NullPointerException e) { System.out.println("TreeMap.put(null,..): NullPointerException"); }

        System.out.println("-- 4. mutating an element inside the queue");
        PriorityQueue<Mutable> mq = new PriorityQueue<>(Comparator.comparingInt((Mutable m) -> m.rank));
        Mutable a = new Mutable(1), b = new Mutable(2), c = new Mutable(3);
        mq.add(a); mq.add(b); mq.add(c);
        c.rank = 0;                                  // c should now be first
        System.out.println("poll -> " + mq.poll() + " (expected r0)");

        System.out.println("-- 5. TreeMap uses the comparator for equality");
        TreeMap<Ticket, String> byPriority = new TreeMap<>(Comparator.comparing(Ticket::priority));
        for (Ticket t : Main.sample()) byPriority.put(t, t.title());
        System.out.println("6 tickets in, size = " + byPriority.size());

        System.out.println("-- 6. headMap is a live view");
        TreeMap<Integer, String> m = new TreeMap<>(Map.of(10, "a", 20, "b", 30, "c"));
        NavigableMap<Integer, String> head = m.headMap(25, true);
        m.put(15, "new");
        System.out.println("head after put(15): " + head);
        try { head.put(99, "x"); } catch (IllegalArgumentException e) { System.out.println("head.put(99): IllegalArgumentException: " + e.getMessage()); }

        System.out.println("-- 7. List.of buckets are immutable");
        TreeMap<Integer, List<String>> bad = new TreeMap<>();
        bad.put(1, List.of("a"));
        try { bad.get(1).add("b"); } catch (UnsupportedOperationException e) { System.out.println("UnsupportedOperationException"); }
    }
}

-- 1. toString of a PriorityQueue
[1, 2, 4, 5, 3]  <- not sorted
-- 2. no Comparator, not Comparable
ClassCastException: class Traps$Plain cannot be cast to class java.lang.Comparable (Traps$Plain is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
-- 3. null element / null key
PriorityQueue.add(null): NullPointerException
TreeMap.put(null,..): NullPointerException
-- 4. mutating an element inside the queue
poll -> r1 (expected r0)
-- 5. TreeMap uses the comparator for equality
6 tickets in, size = 4
-- 6. headMap is a live view
head after put(15): {10=a, 15=new, 20=b}
head.put(99): IllegalArgumentException: key out of range
-- 7. List.of buckets are immutable
UnsupportedOperationException

1. toString() on a PriorityQueue is not sorted. [1, 2, 4, 5, 3] from the numbers 5, 1, 4, 2, 3. The Javadoc says the iterator makes no promise about order, and toString walks it. Drain a copy, or sort a list, when you need to display it.
2. No comparator and no Comparable. The message ends with the unhelpful cannot be cast to class java.lang.Comparable. Notice it fires on the first add, not at construction. Pass a comparator to the constructor, or make the element type comparable.
3. Null is rejected. Both PriorityQueue.add(null) and a TreeMap with natural ordering throw NullPointerException. A TreeMap with a custom comparator can accept a null key if your comparator handles it; I wouldn't.
4. Mutating an element inside the queue. I changed the third element's rank to 0 after inserting it, then polled. Out came r1, not r0. The heap doesn't know the key changed and doesn't re-sort. This one has no exception, no warning, and it shows up weeks later as "tickets seem to be worked out of order". Remove and re-add, or use immutable elements, as the record does.
5. TreeMap treats comparator-equal keys as the same key. Six tickets went into a map whose comparator looked at priority only; four came out. Three of them silently overwrote each other. If you want tickets as keys, the comparator has to be a total order, which is why WORK_ORDER ends with the id.
6. headMap, tailMap and subMap are live views. After put(15, "new") on the parent, the earlier headMap shows 15. And writing outside the view's range throws IllegalArgumentException: key out of range. Copy into a new map (new TreeMap<>(m.headMap(25))) if you need a snapshot.
7. List.of as a bucket value. I wrote computeIfAbsent(..., k -> new ArrayList<>()) in SlaBoard for a reason: with List.of("a") as the value, adding a second ticket to the bucket throws UnsupportedOperationException.

Before real traffic hits it

• remove(Object) is O(n). With a few thousand tickets that's fine. With a million, you want an index from id to position, or a different structure.
• Not thread-safe. Two threads adding to the same PriorityQueue can corrupt it. Wrap access in a lock or switch to PriorityBlockingQueue.
• Pick the right order for ties. Without the id tiebreaker, equal-priority tickets come out in an order that depends on insertion history, and your support team will notice before your tests do.
• Tickets are in memory only. A restart loses the queue. That's a persistence question, not a collection question.
• TreeMap vs LinkedHashMap. If you only need insertion order, how to use LinkedHashMap is cheaper. If you need sorted order, you're in the right place.
• Version note. On Java 21 TreeMap also implements SequencedMap, so firstEntry(), lastEntry() and reversed() are available. Nothing here depends on them, and the code compiles on 17 unchanged.

Next in the series: enum-keyed maps with EnumMap and EnumSet would be a good fit for Priority, since it's already an enum.

Rules to keep

• Create the queue with a comparator and give it a tiebreaker so the order is total.
• Treat PriorityQueue iteration order as meaningless; drain a copy to display.
• Never change a field that feeds the comparator while the element is inside. Remove, change, add.
• A TreeMap comparator defines key identity. Make it fine-grained enough that distinct keys stay distinct.
• Use headMap, subMap, higherKey and floorKey instead of looping over entries; and mind the inclusive flags.

Questions about PriorityQueue and TreeMap

Is PriorityQueue sorted in Java?
Only at the front. peek and poll always give the smallest element according to the ordering, but iterating or printing the queue shows heap order. Drain a copy to get a full sort.

What's the difference between PriorityQueue and TreeMap?
A PriorityQueue gives fast access to the one smallest element and stores duplicates freely. A TreeMap keeps unique keys fully sorted and supports range and neighbour queries. Use the queue to consume, the map to look around.

How do I update an element's priority in a PriorityQueue?
Remove it, build a changed copy, and add that. Changing a field in place leaves the heap in the wrong order, as trap 4 shows. remove is O(n), so it's fine for small queues.

Can a TreeMap have duplicate keys?
No. Keys that the comparator says are equal collapse into one entry. If you need several values per key, make the value a list, as SlaBoard does.

Is TreeMap thread-safe?
No. Use ConcurrentSkipListMap for a sorted concurrent map, or guard the TreeMap with a lock.

References

• Java SE 21 API: PriorityQueue, TreeMap, NavigableMap
• Java SE 21 API: Comparator