NavigableMap and NavigableSet: floor, ceiling, range queries

NavigableMap and NavigableSet extend SortedMap and SortedSet with navigation methods that answer questions like 'what is the closest key less than X?' or 'give me all entries between A and B inclusive?'. TreeMap and TreeSet are the standard implementations: both backed by a Red-Black tree, providing O(log n) for all operations. These interfaces are the right choice whenever your algorithm needs ordered data, proximity queries, or sliding-window range scans.

NavigableMap Interface: floor, ceiling, lower, higher
headMap / tailMap / subMap
descendingMap and descendingKeySet
pollFirstEntry and pollLastEntry
NavigableSet: floor, ceiling, lower, higher
headSet / tailSet / subSet
TreeMap as NavigableMap, TreeSet as NavigableSet
Practical Examples: Time-range Lookup and Leaderboard

NavigableMap Interface: floor, ceiling, lower, higher

NavigableMap extends SortedMap with four proximity methods that answer nearest-key questions. floorKey(k) returns the greatest key ≤ k; ceilingKey(k) returns the smallest key ≥ k. lowerKey(k) and higherKey(k) are strictly exclusive versions. Each method also has an *Entry variant that returns the full Map.Entry<K,V> in one tree traversal: more efficient than calling the key variant and then get(). All return null when no qualifying key exists.

Java

import java.util.*;

// NavigableMap adds four proximity methods on top of SortedMap:
//   floorKey(k)   — greatest key <= k  (null if none)
//   ceilingKey(k) — smallest key >= k  (null if none)
//   lowerKey(k)   — greatest key <  k  (strictly less, null if none)
//   higherKey(k)  — smallest key >  k  (strictly greater, null if none)
// Each also has an *Entry variant returning Map.Entry<K,V>

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "ten");
tm.put(20, "twenty");
tm.put(30, "thirty");
tm.put(40, "forty");
tm.put(50, "fifty");

// --- Key-only variants ---
System.out.println(tm.floorKey(25));    // 20  (greatest key <= 25)
System.out.println(tm.floorKey(20));    // 20  (exact match counts)
System.out.println(tm.floorKey(5));     // null (nothing <= 5)

System.out.println(tm.ceilingKey(25));  // 30  (smallest key >= 25)
System.out.println(tm.ceilingKey(30));  // 30  (exact match counts)
System.out.println(tm.ceilingKey(55));  // null (nothing >= 55)

System.out.println(tm.lowerKey(30));    // 20  (strictly < 30)
System.out.println(tm.lowerKey(10));    // null (nothing strictly < 10)

System.out.println(tm.higherKey(30));   // 40  (strictly > 30)
System.out.println(tm.higherKey(50));   // null (nothing strictly > 50)

// --- Entry variants (key + value together) ---
Map.Entry<Integer, String> floorEntry   = tm.floorEntry(25);
Map.Entry<Integer, String> ceilingEntry = tm.ceilingEntry(25);
System.out.println(floorEntry);   // 20=twenty
System.out.println(ceilingEntry); // 30=thirty

// Practical: find the price tier for a spend amount
TreeMap<Integer, String> priceTiers = new TreeMap<>();
priceTiers.put(0,   "Free");
priceTiers.put(10,  "Starter");
priceTiers.put(50,  "Pro");
priceTiers.put(200, "Enterprise");

int spend = 75;
Map.Entry<Integer, String> tier = priceTiers.floorEntry(spend);
System.out.println("Tier: " + tier.getValue()); // Pro (greatest threshold <= 75)

// Edge case: spend below all tiers
Map.Entry<Integer, String> below = priceTiers.floorEntry(-1);
System.out.println(below); // null — handle carefully

All four methods return null when no qualifying key exists. The entry variants are more efficient than calling the key variant followed by get() because they retrieve the value in the same tree traversal.

headMap / tailMap / subMap

NavigableMap provides three range-view methods that return a live, backed sub-map, not a copy. headMap(toKey) gives all entries with keys strictly less than toKey; pass a second boolean argument to make the boundary inclusive. tailMap(fromKey) gives entries from fromKey onward (inclusive by default). subMap(from, to) returns a half-open [from, to) window; the overload with two booleans lets you control inclusivity on both ends. Because these views are live, any write through the view updates the original map and vice versa.

Java

TreeMap<Integer, String> tm = new TreeMap<>();
for (int i = 10; i <= 100; i += 10) {
    tm.put(i, "val-" + i);
}
// Keys: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100

// headMap(toKey) — keys STRICTLY less than toKey (exclusive by default)
SortedMap<Integer, String> head = tm.headMap(40);
System.out.println(head.keySet()); // [10, 20, 30]

// headMap(toKey, inclusive) — keys <= toKey when inclusive=true
NavigableMap<Integer, String> headInclusive = tm.headMap(40, true);
System.out.println(headInclusive.keySet()); // [10, 20, 30, 40]

// tailMap(fromKey) — keys >= fromKey (inclusive by default)
SortedMap<Integer, String> tail = tm.tailMap(70);
System.out.println(tail.keySet()); // [70, 80, 90, 100]

// tailMap(fromKey, inclusive) — keys > fromKey when inclusive=false
NavigableMap<Integer, String> tailExclusive = tm.tailMap(70, false);
System.out.println(tailExclusive.keySet()); // [80, 90, 100]

// subMap(fromKey, toKey) — [fromKey, toKey)  half-open by default
SortedMap<Integer, String> sub = tm.subMap(30, 70);
System.out.println(sub.keySet()); // [30, 40, 50, 60]

// subMap with explicit inclusivity — fully closed [30, 70]
NavigableMap<Integer, String> closedSub = tm.subMap(30, true, 70, true);
System.out.println(closedSub.keySet()); // [30, 40, 50, 60, 70]

// Views are LIVE — modifications reflect in the original map
sub.put(35, "thirty-five"); // adds 35 to tm
System.out.println(tm.containsKey(35)); // true

// Modifications outside the view's range throw IllegalArgumentException
// sub.put(80, "eighty"); // throws — 80 outside [30, 70)

// Using headMap/tailMap for range counts
long countBetween30And70 = tm.subMap(30, true, 70, true).size();
System.out.println("Keys in [30,70]: " + countBetween30And70); // 5 (30,35,40,50,60,70)

Range views returned by headMap, tailMap, and subMap are live, backed views of the original map, not copies. Structural changes through the view modify the underlying map, and iterating the original map reflects keys added through the view. Create a copy with new TreeMap<>(sub) when you need an independent snapshot.

descendingMap and descendingKeySet

descendingMap() returns a live NavigableMap view with the key order reversed, iterating it goes from the largest key to the smallest. descendingKeySet() returns the same idea as a NavigableSet. All navigation methods (floor, ceiling, headMap, etc.) work on the descending view, but their semantics flip: firstKey() on the descending view returns what was the last key in the original. Both views are live: mutations are reflected in both directions.

Java

TreeMap<String, Integer> scores = new TreeMap<>();
scores.put("Alice",  92);
scores.put("Bob",    78);
scores.put("Carol",  85);
scores.put("Diana",  95);
scores.put("Ethan",  71);

// descendingMap — returns a live view with reversed key order
NavigableMap<String, Integer> desc = scores.descendingMap();
desc.forEach((name, score) ->
    System.out.println(name + ": " + score));
// Ethan: 71  Diana: 95  Carol: 85  Bob: 78  Alice: 92  (Z→A)

// descendingKeySet — NavigableSet of keys in reverse order
NavigableSet<String> reverseKeys = scores.descendingKeySet();
System.out.println(reverseKeys.first()); // "Ethan"  (last in natural order)
System.out.println(reverseKeys.last());  // "Alice"  (first in natural order)

// Get top-3 scorers: sort by score descending, limit 3
scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .limit(3)
    .forEach(e -> System.out.println(e.getKey() + ": " + e.getValue()));
// Diana: 95  Alice: 92  Carol: 85

// Reverse iteration over keys using descendingKeySet
for (String name : scores.descendingKeySet()) {
    System.out.println(name + " = " + scores.get(name));
}

// descendingMap is also NavigableMap — all navigation methods work in reverse
NavigableMap<String, Integer> descView = scores.descendingMap();
System.out.println(descView.firstKey()); // Ethan (last alphabetically)
System.out.println(descView.floorKey("Charlie")); // Carol (greatest reversed key <= Charlie)

// headMap on a descending view: keys >= threshold in original order
NavigableMap<String, Integer> afterCarol = descView.tailMap("Carol", true);
System.out.println(afterCarol.keySet()); // [Carol, Bob, Alice] (descending, from Carol)

pollFirstEntry and pollLastEntry

pollFirstEntry() atomically removes and returns the entry with the smallest key; pollLastEntry() does the same for the largest key. Both return null on an empty map: unlike firstEntry()/lastEntry() which only peek without removing. This makes them the idiomatic building block for a sorted task queue or priority scheduler: keep polling the front (or back) until empty or a condition is met.

Java

// pollFirstEntry() — removes AND returns the entry with the smallest key
// pollLastEntry()  — removes AND returns the entry with the largest key
// Return null if the map is empty (unlike firstEntry/lastEntry which throw)

TreeMap<Integer, String> tasks = new TreeMap<>();
tasks.put(1,  "critical");
tasks.put(5,  "high");
tasks.put(10, "medium");
tasks.put(20, "low");

// Process tasks in priority order (lowest number = highest priority)
Map.Entry<Integer, String> next;
while ((next = tasks.pollFirstEntry()) != null) {
    System.out.println("Processing [" + next.getKey() + "] " + next.getValue());
}
// Processing [1] critical
// Processing [5] high
// Processing [10] medium
// Processing [20] low
// (map is now empty)

// pollLastEntry — useful for max-priority-first processing
TreeMap<Integer, String> bids = new TreeMap<>();
bids.put(100, "buyer-A");
bids.put(150, "buyer-B");
bids.put(120, "buyer-C");
bids.put(200, "buyer-D");

// Accept highest bids first until budget exhausted
int budget = 350;
Map.Entry<Integer, String> topBid;
while (!bids.isEmpty() && (topBid = bids.pollLastEntry()) != null) {
    if (budget >= topBid.getKey()) {
        budget -= topBid.getKey();
        System.out.println("Accepted bid " + topBid.getKey() + " from " + topBid.getValue());
    } else {
        System.out.println("Skipped bid " + topBid.getKey() + " — over budget");
        break;
    }
}
// Accepted bid 200 from buyer-D
// Accepted bid 150 from buyer-B (budget now 0)
// Skipped bid 120 — over budget

// firstEntry / lastEntry — peek without removing
TreeMap<String, Integer> tm = new TreeMap<>(Map.of("a", 1, "z", 26, "m", 13));
System.out.println(tm.firstEntry()); // a=1   (peek)
System.out.println(tm.lastEntry());  // z=26  (peek)
System.out.println(tm.size());       // 3     (unchanged)

pollFirstEntry() and pollLastEntry() are the idiomatic way to implement a sorted work queue or priority scheduler in a single-threaded context. For concurrent use, consider ConcurrentSkipListMap which also implements NavigableMap and is thread-safe.

NavigableSet: floor, ceiling, lower, higher

NavigableSet extends SortedSet with the same four proximity methods as NavigableMap, but operating on elements instead of keys: floor(e), ceiling(e), lower(e), and higher(e). pollFirst() and pollLast() remove and return the smallest and largest elements. descendingSet() gives a live reverse-order view. TreeSet is the standard implementation.

Java

import java.util.*;

// NavigableSet adds the same proximity methods as NavigableMap, but for sets only
//   floor(e)   — greatest element <= e
//   ceiling(e) — smallest element >= e
//   lower(e)   — greatest element <  e (strictly)
//   higher(e)  — smallest element >  e (strictly)

TreeSet<Integer> ts = new TreeSet<>(Set.of(10, 20, 30, 40, 50));

System.out.println(ts.floor(25));    // 20
System.out.println(ts.floor(30));    // 30  (exact match)
System.out.println(ts.floor(5));     // null

System.out.println(ts.ceiling(25));  // 30
System.out.println(ts.ceiling(30));  // 30  (exact match)
System.out.println(ts.ceiling(55));  // null

System.out.println(ts.lower(30));    // 20  (strictly < 30)
System.out.println(ts.higher(30));   // 40  (strictly > 30)

// pollFirst() / pollLast() — remove and return smallest/largest
TreeSet<String> words = new TreeSet<>(Set.of("apple", "banana", "cherry", "date"));
System.out.println(words.pollFirst()); // apple   (removed)
System.out.println(words.pollLast());  // date    (removed)
System.out.println(words); // [banana, cherry]

// first() / last() — peek without removing
TreeSet<Integer> nums = new TreeSet<>(Set.of(5, 3, 8, 1, 9));
System.out.println(nums.first()); // 1
System.out.println(nums.last());  // 9
System.out.println(nums.size());  // 5 (unchanged)

// descendingSet() — live reversed view
NavigableSet<Integer> descNums = nums.descendingSet();
System.out.println(descNums.first()); // 9
descNums.forEach(System.out::println); // 9, 8, 5, 3, 1

headSet / tailSet / subSet

NavigableSet mirrors the map range-view methods. headSet(toElement) returns all elements strictly less than toElement; pass true as the second argument to make it inclusive. tailSet(fromElement) returns elements from fromElement upward. subSet(from, to) returns a half-open range by default; the four-argument overload gives full control over both boundaries. Like map views, all set views are live and backed by the original: writes through the view affect the source set.

Java

TreeSet<Integer> ts = new TreeSet<>();
for (int i = 10; i <= 100; i += 10) ts.add(i);
// {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}

// headSet(toElement) — elements STRICTLY less than toElement
SortedSet<Integer> head = ts.headSet(50);
System.out.println(head); // [10, 20, 30, 40]

// headSet(toElement, inclusive)
NavigableSet<Integer> headInc = ts.headSet(50, true);
System.out.println(headInc); // [10, 20, 30, 40, 50]

// tailSet(fromElement) — elements >= fromElement
SortedSet<Integer> tail = ts.tailSet(70);
System.out.println(tail); // [70, 80, 90, 100]

// tailSet(fromElement, inclusive=false) — strictly > fromElement
NavigableSet<Integer> tailExcl = ts.tailSet(70, false);
System.out.println(tailExcl); // [80, 90, 100]

// subSet(from, to) — [from, to) half-open
SortedSet<Integer> sub = ts.subSet(30, 70);
System.out.println(sub); // [30, 40, 50, 60]

// subSet with explicit inclusivity — closed [30, 70]
NavigableSet<Integer> closedSub = ts.subSet(30, true, 70, true);
System.out.println(closedSub); // [30, 40, 50, 60, 70]

// Live views — adds through sub appear in the original set
closedSub.add(35);
System.out.println(ts.contains(35)); // true

// Count elements in a range
int count = ts.subSet(20, true, 60, true).size(); // [20,60] = 5 elements
System.out.println("Elements in [20,60]: " + count);

// Iterate range without creating a subSet
for (Integer k = ts.ceiling(25); k != null && k <= 65; k = ts.higher(k)) {
    System.out.print(k + " "); // 30 35 40 50 60
}

TreeMap as NavigableMap, TreeSet as NavigableSet

TreeMap is the standard NavigableMap implementation, backed by a Red-Black tree with O(log n) for all operations. It accepts a custom Comparator at construction time to override natural ordering. TreeSet is backed internally by a TreeMap and implements NavigableSet. One important rule: if a Comparator considers two elements equal (returns 0), the tree treats them as the same key, regardless of what equals() says. For concurrent workloads, ConcurrentSkipListMap / ConcurrentSkipListSet implement the same interfaces with lock-free thread safety.

Java

import java.util.*;

// TreeMap — Red-Black tree
// Implements: NavigableMap → SortedMap → Map
// All operations: O(log n)
// No null keys (compareTo would NPE); null values allowed

// Custom comparator — reverse alphabetical key order
TreeMap<String, Integer> reverseAlpha =
    new TreeMap<>(Comparator.reverseOrder());
reverseAlpha.put("apple", 1);
reverseAlpha.put("cherry", 3);
reverseAlpha.put("banana", 2);
reverseAlpha.forEach((k, v) -> System.out.println(k)); // cherry, banana, apple

// TreeSet — backed by a TreeMap internally
// Implements: NavigableSet → SortedSet → Set
// Custom ordering
TreeSet<String> byLength = new TreeSet<>(
    Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder()));
byLength.addAll(List.of("banana", "fig", "apple", "kiwi", "cherry", "ox"));
System.out.println(byLength); // [ox, fig, kiwi, apple, banana, cherry] (len asc, then alpha)

// Comparator consistency with equals:
// If two elements compare as 0 by the comparator, TreeSet treats them as duplicates
// Even if equals() says they are different objects
TreeSet<String> caseInsensitive = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
caseInsensitive.add("Hello");
caseInsensitive.add("hello"); // treated as duplicate — not added
System.out.println(caseInsensitive.size()); // 1
System.out.println(caseInsensitive); // [Hello]

// TreeMap from existing map (copy constructor)
Map<String, Integer> source = Map.of("c", 3, "a", 1, "b", 2);
TreeMap<String, Integer> sorted = new TreeMap<>(source);
System.out.println(sorted); // {a=1, b=2, c=3}

// ConcurrentSkipListMap / ConcurrentSkipListSet for concurrent NavigableMap/Set
// java.util.concurrent.ConcurrentSkipListMap implements NavigableMap, is thread-safe
// O(log n) expected, but lock-free — better throughput under contention than TreeMap

When two elements compare as equal via the supplied Comparator, TreeSet and TreeMap treat them as the same key. For TreeSet this means the second element is not inserted. Always ensure your comparator is consistent with equals() unless the "duplicate by ordering" behavior is intentional.

Practical Examples: Time-range Lookup and Leaderboard

Three patterns that show up frequently in real code: querying a time-ordered event log with subMap and floorEntry, implementing a score-based leaderboard with reverse-ordered TreeMap and headMap for rank calculation, and counting or iterating distinct values in a sorted window using TreeSet.subSet.

Java

import java.util.*;
import java.time.*;

// --- Example 1: Event log — find events in a time range ---
record LogEvent(Instant time, String message) {}

TreeMap<Instant, LogEvent> eventLog = new TreeMap<>();
Instant base = Instant.parse("2026-03-14T10:00:00Z");

eventLog.put(base.plusSeconds(0),   new LogEvent(base.plusSeconds(0),   "Server started"));
eventLog.put(base.plusSeconds(30),  new LogEvent(base.plusSeconds(30),  "Request received"));
eventLog.put(base.plusSeconds(65),  new LogEvent(base.plusSeconds(65),  "DB query executed"));
eventLog.put(base.plusSeconds(120), new LogEvent(base.plusSeconds(120), "Response sent"));
eventLog.put(base.plusSeconds(180), new LogEvent(base.plusSeconds(180), "Connection closed"));

Instant from = base.plusSeconds(25);
Instant to   = base.plusSeconds(130);

// All events in [from, to] inclusive
NavigableMap<Instant, LogEvent> window = eventLog.subMap(from, true, to, true);
window.forEach((t, e) ->
    System.out.println(t.getEpochSecond() - base.getEpochSecond() + "s: " + e.message()));
// 30s: Request received
// 65s: DB query executed
// 120s: Response sent

// Most recent event before a given time
Instant query = base.plusSeconds(100);
Map.Entry<Instant, LogEvent> latest = eventLog.floorEntry(query);
System.out.println("Most recent before T+100: " + latest.getValue().message());
// Most recent before T+100: DB query executed

// Next event after a given time
Map.Entry<Instant, LogEvent> next = eventLog.higherEntry(query);
System.out.println("Next after T+100: " + next.getValue().message());
// Next after T+100: Response sent

// --- Example 2: Leaderboard — top-N retrieval and rank queries ---
TreeMap<Integer, String> leaderboard = new TreeMap<>(Comparator.reverseOrder());
leaderboard.put(9500, "Alice");
leaderboard.put(8200, "Bob");
leaderboard.put(7800, "Carol");
leaderboard.put(9100, "Diana");
leaderboard.put(6500, "Ethan");
leaderboard.put(9500, "Fiona"); // same score as Alice — overwrites in TreeMap

// Top 3 scores
leaderboard.entrySet().stream()
    .limit(3)
    .forEach(e -> System.out.println(e.getValue() + ": " + e.getKey()));
// Fiona: 9500  Diana: 9100  Bob: 8200

// Rank of a player: how many players have strictly higher scores?
int carolScore = 7800;
int rank = leaderboard.headMap(carolScore, false).size() + 1; // exclusive = strictly higher
System.out.println("Carol's rank: " + rank); // 3

// Players within 500 points of Bob
int bobScore = 8200;
NavigableMap<Integer, String> nearBob = leaderboard.subMap(
    bobScore - 500, true,
    bobScore + 500, true);
System.out.println("Near Bob: " + nearBob.values()); // [Bob] (none within 500 in this set)

// --- Example 3: NavigableSet for a sliding-window unique-count ---
// Count distinct values in a sorted window using TreeSet subSet
TreeSet<Integer> window2 = new TreeSet<>(Set.of(1, 3, 5, 7, 9, 11, 13, 15, 17, 19));

int lo = 5, hi = 15;
int countInRange = window2.subSet(lo, true, hi, true).size();
System.out.println("Elements in [" + lo + "," + hi + "]: " + countInRange); // 6

// Nearest value to a target that is in the set
int target = 10;
Integer floorVal   = window2.floor(target);    // 9
Integer ceilingVal = window2.ceiling(target);  // 11
int closest = (floorVal == null) ? ceilingVal
    : (ceilingVal == null) ? floorVal
    : (target - floorVal <= ceilingVal - target) ? floorVal : ceilingVal;
System.out.println("Closest to " + target + ": " + closest); // 9 or 11 (tie → 9)

Contents

NavigableMap Interface: floor, ceiling, lower, higher

headMap / tailMap / subMap

descendingMap and descendingKeySet

pollFirstEntry and pollLastEntry

NavigableSet: floor, ceiling, lower, higher

headSet / tailSet / subSet

TreeMap as NavigableMap, TreeSet as NavigableSet

Practical Examples: Time-range Lookup and Leaderboard

Related articles