Java.Collections.What is SortedSet ?

SortedSet<E> is an interface in the Java Collections Framework that extends Set<E> and guarantees that its elements are sorted in ascending order (natural ordering or a custom comparator).

It is useful when you need:

• A Set (i.e., no duplicate elements) with sorting.
• Efficient operations like first, last, subset extraction.

---

1. Key Features of SortedSet

✅ No duplicate elements (like any Set).
✅ Maintains elements in sorted order (natural order or via Comparator).
✅ Provides additional methods for retrieval and range queries.

---

2. SortedSet Interface Definition

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();  // Returns comparator used for sorting, or null if natural order
    E first();  // Retrieves first (lowest) element
    E last();   // Retrieves last (highest) element
    SortedSet<E> headSet(E toElement);  // Returns a view of elements less than toElement
    SortedSet<E> tailSet(E fromElement); // Returns a view of elements greater than or equal to fromElement
    SortedSet<E> subSet(E fromElement, E toElement);  // Returns a subset in range
}

3. Implementation: TreeSet (Most Common)

TreeSet<E> is the primary implementation of SortedSet<E> and is based on a Red-Black Tree, ensuring logarithmic time complexity for operations.

Example 1: Natural Ordering

import java.util.SortedSet;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        SortedSet<Integer> numbers = new TreeSet<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(9);
        numbers.add(1);

        System.out.println(numbers);  // Output: [1, 2, 5, 9] (Sorted order)

        // Retrieving elements
        System.out.println("First: " + numbers.first());  // Output: 1
        System.out.println("Last: " + numbers.last());    // Output: 9

        // Subsets
        System.out.println("HeadSet(5): " + numbers.headSet(5));  // Output: [1, 2]
        System.out.println("TailSet(5): " + numbers.tailSet(5));  // Output: [5, 9]
        System.out.println("SubSet(2, 9): " + numbers.subSet(2, 9)); // Output: [2, 5]
    }
}

Example 2: Custom Sorting Using Comparator

If you need a different sorting order (e.g., descending), use a custom Comparator.

import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        // Custom Comparator for descending order
        SortedSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());
        numbers.add(5);
        numbers.add(2);
        numbers.add(9);
        numbers.add(1);

        System.out.println(numbers);  // Output: [9, 5, 2, 1] (Sorted in descending order)
    }
}

4. Differences Between HashSet, LinkedHashSet, and TreeSet

Feature	HashSet	LinkedHashSet	TreeSet (SortedSet)
Ordering	Unordered	Insertion order	Sorted (ascending by default)
Duplicates	❌ No	❌ No	❌ No
Sorting	❌ No	❌ No	✅ Yes
Performance (Add/Remove/Search)	O(1)	O(1)	O(log n) (Red-Black Tree)
Implements SortedSet?	❌ No	❌ No	✅ Yes

---

5. When to Use SortedSet?

• When you need to maintain elements in sorted order.
• When you need efficient range queries (e.g., subSet, headSet, tailSet).
• When duplicates must not be allowed.

---

Final Thoughts

• SortedSet<E> extends Set<E> but guarantees sorting.
• TreeSet<E> is the most common implementation, using a self-balancing tree (Red-Black Tree).
• You can use natural ordering or custom comparators for sorting.
• Logarithmic time complexity (O(log n)) for insertions, deletions, and searches.