Sorted Maps, Sets, and Priority Queues

A HashMap finds a key in O(1) but keeps no order. A sorted collection keeps its elements ordered by a comparison, which costs O(log n) per operation and adds range queries: "the largest key at or below x", "all keys between a and b". This lesson covers TreeMap and TreeSet, the NavigableMap queries, the rule that a comparator must agree with equals, PriorityQueue, and SequencedMap. Terms such as bucket and load factor come from HashMap Internals.

Class	Structure	Ordered by
`TreeMap`, `TreeSet`	red-black tree	key comparison, full order on iteration
`PriorityQueue`	binary heap in an array	comparison, only the head is ordered
`LinkedHashMap`	hash table plus linked list	insertion or access order
`ConcurrentSkipListMap`	skip list	key comparison, thread safe

Example 1: TreeMap keeps keys sorted

TreeMap is a red-black tree: a binary search tree that colors nodes red or black and rebalances on insert and delete so the height stays at most about 2 log2(n). get, put, and remove are O(log n). Iteration visits keys in ascending order. Keys are compared with compareTo (natural ordering) or with a Comparator passed to the constructor.

Java

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapBasics {
    public static void main(String[] args) {
        Map<String, Integer> natural = new TreeMap<>();
        for (String s : new String[]{"pear", "apple", "fig", "banana"}) natural.put(s, s.length());
        System.out.println("natural:  " + natural);

        Map<String, Integer> byLength = new TreeMap<>(
                Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
        byLength.putAll(natural);
        System.out.println("byLength: " + byLength);

        TreeMap<String, Integer> reversed = new TreeMap<>(Comparator.reverseOrder());
        reversed.putAll(natural);
        System.out.println("reversed: " + reversed);
        System.out.println("first and last: " + reversed.firstKey() + " " + reversed.lastKey());
    }
}

Output

natural:  {apple=5, banana=6, fig=3, pear=4}
byLength: {fig=3, pear=4, apple=5, banana=6}
reversed: {pear=4, fig=3, banana=6, apple=5}
first and last: pear apple

TreeMap rejects a null key with natural ordering, because compareTo cannot be called on null. A TreeMap created without a comparator also requires keys to implement Comparable, and the failure shows up as a ClassCastException on the first put.

Example 2: NavigableMap queries

NavigableMap (implemented by TreeMap) adds nearest-key lookups and views over key ranges. All of them run in O(log n).

Method	Returns
`floorKey(k)`	greatest key `<= k`, or `null`
`lowerKey(k)`	greatest key `< k`
`ceilingEntry(k)`	entry with least key `>= k`
`higherKey(k)`	least key `> k`
`headMap(k)`	keys `< k` (`headMap(k, true)` includes `k`)
`tailMap(k)`	keys `>= k`
`subMap(a, b)`	keys in `[a, b)`
`descendingMap()`	the same map in reverse order

Java

import java.util.NavigableMap;
import java.util.TreeMap;

public class Navigable {
    public static void main(String[] args) {
        NavigableMap<Integer, String> m = new TreeMap<>();
        for (int k : new int[]{10, 20, 30, 40, 50}) m.put(k, "v" + k);

        System.out.println("floorKey(25)    = " + m.floorKey(25));
        System.out.println("lowerKey(20)    = " + m.lowerKey(20));
        System.out.println("ceilingEntry(25)= " + m.ceilingEntry(25));
        System.out.println("higherKey(50)   = " + m.higherKey(50));
        System.out.println("headMap(30)     = " + m.headMap(30));
        System.out.println("headMap(30,true)= " + m.headMap(30, true));
        System.out.println("tailMap(40)     = " + m.tailMap(40));
        System.out.println("subMap(20,40)   = " + m.subMap(20, 40));
        System.out.println("descendingMap   = " + m.descendingMap());

        NavigableMap<Integer, String> view = m.subMap(20, true, 40, true);
        m.put(35, "v35");                   // views are live
        view.remove(20);                    // and write through
        System.out.println("view after edits= " + view);
        System.out.println("map after edits = " + m);
    }
}

Output

floorKey(25)    = 20
lowerKey(20)    = 10
ceilingEntry(25)= 30=v30
higherKey(50)   = null
headMap(30)     = {10=v10, 20=v20}
headMap(30,true)= {10=v10, 20=v20, 30=v30}
tailMap(40)     = {40=v40, 50=v50}
subMap(20,40)   = {20=v20, 30=v30}
descendingMap   = {50=v50, 40=v40, 30=v30, 20=v20, 10=v10}
view after edits= {30=v30, 35=v35, 40=v40}
map after edits = {10=v10, 30=v30, 35=v35, 40=v40, 50=v50}

A range view is backed by the original tree. Putting a key outside the view's range through the view throws IllegalArgumentException.

Example 3: TreeSet and a comparator that disagrees with equals

TreeSet wraps a TreeMap, the same way HashSet wraps a HashMap. A sorted collection decides that two elements are the same when compare returns 0; it never calls equals. A comparator is consistent with equals when compare(a, b) == 0 exactly when a.equals(b). If it is not, the set silently drops elements that are not equal.

Java

import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Consistency {
    record Order(String id, long price) {}

    public static void main(String[] args) {
        List<Order> orders = List.of(new Order("A", 100), new Order("B", 100), new Order("C", 99));

        Set<Order> hash = new HashSet<>(orders);
        Set<Order> byPriceOnly = new TreeSet<>(Comparator.comparingLong(Order::price));
        byPriceOnly.addAll(orders);
        Set<Order> byPriceThenId = new TreeSet<>(
                Comparator.comparingLong(Order::price).thenComparing(Order::id));
        byPriceThenId.addAll(orders);

        System.out.println("HashSet size:          " + hash.size());
        System.out.println("TreeSet price only:    " + byPriceOnly.size() + " " + byPriceOnly);
        System.out.println("TreeSet price then id: " + byPriceThenId.size());
        System.out.println("contains B (price only): "
                + byPriceOnly.contains(new Order("B", 100)));

        System.out.println("BigDecimal 1.0 vs 1.00 in TreeSet: "
                + new TreeSet<>(List.of(new java.math.BigDecimal("1.0"),
                                        new java.math.BigDecimal("1.00"))).size()
                + ", in HashSet: "
                + new HashSet<>(List.of(new java.math.BigDecimal("1.0"),
                                        new java.math.BigDecimal("1.00"))).size());
    }
}

Output

HashSet size:          3
TreeSet price only:    2 [Order[id=C, price=99], Order[id=A, price=100]]
TreeSet price then id: 3
contains B (price only): true
BigDecimal 1.0 vs 1.00 in TreeSet: 1, in HashSet: 2

Order B was dropped because its price compares equal to order A, and contains(B) answers true because it finds A. The fix is a tie-breaker on a unique field. BigDecimal is a JDK class whose natural ordering is not consistent with equals: 1.0 and 1.00 compare as 0 but are not equals, so the two sets disagree on size.

Example 4: PriorityQueue as a binary heap

PriorityQueue stores a binary heap in an array: the element at index i has children at 2i + 1 and 2i + 2, and every parent is less than or equal to its children. The smallest element is at index 0. offer places the element at the end and sifts up (swaps with its parent while smaller). poll moves the last element to the root and sifts down (swaps with the smaller child while larger). Both are O(log n); peek is O(1).

Java

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

public class HeapOrder {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : new int[]{5, 3, 8, 1, 9, 2}) pq.offer(x);

        System.out.println("iterator order (array): " + pq);
        System.out.println("toArray:                " + Arrays.toString(pq.toArray()));
        System.out.println("peek: " + pq.peek());

        List<Integer> polled = new ArrayList<>();
        while (!pq.isEmpty()) polled.add(pq.poll());
        System.out.println("poll order:             " + polled);
    }
}

Output

iterator order (array): [1, 3, 2, 5, 9, 8]
toArray:                [1, 3, 2, 5, 9, 8]
peek: 1
poll order:             [1, 2, 3, 5, 8, 9]

The iterator, toString, and toArray walk the array, which satisfies the heap property but is not sorted. Only repeated poll yields sorted order. remove(Object) and contains are O(n) because they scan the array.

Example 5: a max-heap and top-k

A Comparator turns the min-heap into a max-heap. A common pattern keeps the k largest values of a stream in a min-heap of size k: when the heap is full and a new value beats the smallest kept value, the smallest is replaced. That costs O(n log k) instead of sorting all n values.

Java

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

public class TopK {
    static List<Integer> topK(int[] values, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int v : values) {
            if (minHeap.size() < k) minHeap.offer(v);
            else if (v > minHeap.peek()) { minHeap.poll(); minHeap.offer(v); }
        }
        List<Integer> result = new ArrayList<>(minHeap);
        result.sort(Comparator.reverseOrder());
        return result;
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : new int[]{5, 3, 8, 1}) maxHeap.offer(x);
        System.out.println("max-heap head: " + maxHeap.peek());

        int[] latenciesMicros = {120, 45, 980, 33, 410, 77, 650, 12, 300};
        System.out.println("top 3: " + topK(latenciesMicros, 3));
    }
}

Output

max-heap head: 8
top 3: [980, 650, 410]

Example 6: SequencedMap (Java 21)

Java 21 added SequencedMap: a map with a defined encounter order and methods firstEntry, lastEntry, pollFirstEntry, pollLastEntry, putFirst, putLast, and reversed. SortedMap (and so TreeMap) and LinkedHashMap implement it. A sorted map decides positions by comparison, so putFirst and putLast throw UnsupportedOperationException on TreeMap.

Java

import java.util.LinkedHashMap;
import java.util.SequencedMap;
import java.util.TreeMap;

public class Sequenced {
    public static void main(String[] args) {
        SequencedMap<String, Integer> linked = new LinkedHashMap<>();
        linked.put("b", 2);
        linked.put("c", 3);
        linked.putFirst("a", 1);
        System.out.println("linked:          " + linked);
        System.out.println("reversed view:   " + linked.reversed());
        System.out.println("pollLastEntry:   " + linked.pollLastEntry() + " -> " + linked);

        SequencedMap<String, Integer> tree = new TreeMap<>(linked);
        System.out.println("tree firstEntry: " + tree.firstEntry());
        try {
            tree.putFirst("z", 26);
        } catch (UnsupportedOperationException e) {
            System.out.println("TreeMap.putFirst: UnsupportedOperationException");
        }
    }
}

Output

linked:          {a=1, b=2, c=3}
reversed view:   {c=3, b=2, a=1}
pollLastEntry:   c=3 -> {a=1, b=2}
tree firstEntry: a=1
TreeMap.putFirst: UnsupportedOperationException

TreeMap, TreeSet, and PriorityQueue are not thread safe. ConcurrentSkipListMap and ConcurrentSkipListSet are the sorted concurrent versions; they are covered in Concurrent Collections.

Example 7: an order book side with TreeMap

A price level book keeps, for each price, the total quantity resting there. Bids are sorted highest first, asks lowest first, so firstEntry is the best price on each side. floorKey and ceilingKey answer "the next level a marketable order reaches".

Java

import java.util.Comparator;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class PriceLevels {
    private final NavigableMap<Long, Long> bids = new TreeMap<>(Comparator.reverseOrder());
    private final NavigableMap<Long, Long> asks = new TreeMap<>();

    void add(boolean buy, long price, long qty) {
        (buy ? bids : asks).merge(price, qty, Long::sum);
    }

    void reduce(boolean buy, long price, long qty) {
        NavigableMap<Long, Long> side = buy ? bids : asks;
        side.computeIfPresent(price, (p, q) -> q - qty > 0 ? q - qty : null);  // null removes
    }

    long askQuantityUpTo(long limit) {
        long total = 0;
        for (long q : asks.headMap(limit, true).values()) total += q;
        return total;
    }

    public static void main(String[] args) {
        PriceLevels book = new PriceLevels();
        book.add(true, 9_990, 300);
        book.add(true, 9_995, 100);
        book.add(true, 9_990, 200);
        book.add(false, 10_005, 150);
        book.add(false, 10_010, 400);
        book.add(false, 10_020, 50);

        Map.Entry<Long, Long> bestBid = book.bids.firstEntry();
        Map.Entry<Long, Long> bestAsk = book.asks.firstEntry();
        System.out.println("bids " + book.bids + "  asks " + book.asks);
        System.out.println("best bid " + bestBid + "  best ask " + bestAsk
                + "  spread " + (bestAsk.getKey() - bestBid.getKey()));
        System.out.println("ask qty up to 10010: " + book.askQuantityUpTo(10_010));

        book.reduce(false, 10_005, 150);       // level fully filled
        System.out.println("best ask after fill: " + book.asks.firstEntry());
        System.out.println("first bid level <= 9993: " + book.bids.ceilingKey(9_993L));
    }
}

Output

bids {9995=100, 9990=500}  asks {10005=150, 10010=400, 10020=50}
best bid 9995=100  best ask 10005=150  spread 10
ask qty up to 10010: 550
best ask after fill: 10010=400
first bid level <= 9993: 9990

With the reversed comparator, "next" means lower price, so ceilingKey(9993) on the bid side returns 9990, the highest bid at or below 9993. Each update allocates tree nodes and boxed Long keys; Primitive Collections and Memory Cost measures that cost.

Complexity of common collections

Collection	get or contains	add or put	remove	first or min	Iteration order
`ArrayList`	O(1) by index, O(n) by value	O(1) amortized at end	O(n)	O(1)	insertion
`ArrayDeque`	O(n) by value	O(1) amortized at ends	O(1) at ends	O(1)	insertion
`LinkedList`	O(n)	O(1) at ends	O(1) at ends	O(1)	insertion
`HashMap`, `HashSet`	O(1) average, O(log n) worst in tree bins	O(1) average	O(1) average	not supported	unspecified
`LinkedHashMap`	O(1) average	O(1) average	O(1) average	O(1)	insertion or access
`TreeMap`, `TreeSet`	O(log n)	O(log n)	O(log n)	O(log n)	sorted
`PriorityQueue`	O(n)	O(log n)	O(log n) `poll`, O(n) `remove(o)`	O(1) `peek`	heap array, not sorted
`ConcurrentSkipListMap`	O(log n) expected	O(log n) expected	O(log n) expected	O(1)	sorted

Interview points

TreeMap is a red-black tree; operations are O(log n), iteration is sorted.
floorKey, ceilingKey, lowerKey, higherKey answer nearest-key questions in O(log n); headMap, tailMap, subMap return live views.
Sorted collections use compare, not equals. An inconsistent comparator drops distinct elements; add a tie-breaker on a unique field.
BigDecimal("1.0") and BigDecimal("1.00") are equal to a TreeSet and different to a HashSet.
PriorityQueue is a binary heap in an array; offer and poll are O(log n), peek O(1), remove(Object) O(n). Its iterator is not in priority order.
Top-k of n values: a min-heap of size k, O(n log k).
SequencedMap (Java 21) adds firstEntry, pollLastEntry, reversed; TreeMap.putFirst throws UnsupportedOperationException.
None of these are thread safe; ConcurrentSkipListMap is the sorted concurrent map.

Summary

Sorted maps and sets trade O(1) hashing for O(log n) operations plus order and range queries.
TreeSet wraps TreeMap; equality in both is defined by the comparator.
A heap orders only its head; sorted output needs repeated poll.
SortedMap and LinkedHashMap implement SequencedMap since Java 21.