In modern software development, extracting the top K elements from a large data stream is a frequent requirement. Think of displaying the top 10 trending articles on a news platform, listing the top 3 high scores on a gaming leaderboard, or identifying the top 100 most expensive transactions for fraud detection.

When dealing with dynamically incoming data, sorting the entire list repeatedly is highly inefficient. Instead, we want a data collection that keeps itself sorted on insertion. In Java, this can be achieved efficiently using a TreeSet with a custom comparator, allowing us to keep track of top elements in real-time.

Illustration of an arcade leaderboard showing the top 3 elements
Real-World Analogy: The Arcade Cabinet Leaderboard

To visualize this approach, picture a vintage arcade cabinet running a game. The screen features a High Score Leaderboard containing exactly three slots (K = 3).

As players take turns, they achieve scores. The cabinet manages the board dynamically:

  • When a new score is finished, the system ranks it immediately against the current listings.
  • Standard Java sets (like TreeSet or HashSet) automatically discard duplicates. This means if two different players score exactly 66, the default set will discard one of them.
  • To prevent this, we write a custom comparison rule for our cabinet: "Even if two scores are equal, treat them as separate entries and keep both on the board!"
  • The leaderboard always displays the top 3 entries, letting players know who is currently in the lead.
In code, these arcade scores are our dataset, and the leaderboard is represented by a TreeSet.

TreeSet Strategy & Custom Comparator Gotcha

A TreeSet in Java uses a self-balancing binary search tree (a Red-Black Tree) under the hood. Insertion, deletion, and lookup operations run in O(log N) time.

However, TreeSet relies on a Comparator not only for ordering but also for equality checking. If a comparator returns 0 for two elements, the TreeSet assumes they are duplicates and refuses to add the second element.

To overcome this and allow duplicate scores in our leaderboard, we design a custom comparator that never returns 0:

  • If score o2 is greater than or equal to o1, we return 1 (which forces o2 to be placed before o1, building a descending list).
  • If score o2 is smaller than o1, we return -1.
By returning 1 for equality instead of 0, we bypass the duplicate elimination mechanism and allow duplicates to exist side-by-side in the tree.

Step-by-Step Scenario Walkthrough

Let's trace this execution with an array of scores: [1, 3, 66, 5, 7, 2, 3, 5, 9, 2, 11, 66, 75], targeting K = 3:

  • Populating the Set: We iterate through the array and add each score to the TreeSet.
  • Ordering: The custom comparator sorts the elements descending: [75, 66, 66, 11, 9, 7, 5, 5, 3, 3, 2, 2, 1]. Notice both 66 values are preserved.
  • Extraction: We open an iterator on the set and pull the first K elements. This returns 75, 66, and 66 as the top 3 scores.

Java Implementation Code

Below is the complete Java code demonstrating leaderboard sorting with a custom comparator:

package io.practise.accolite;
 
import java.util.Iterator;
import java.util.TreeSet;
 
public class TopKElements {
 
    public static void main(String[] args) {
        int[] arr = {1, 3, 66, 5, 7, 2, 3, 5, 9, 2, 11, 66, 75};
        int k = 3;
 
        // Self-sorting collection sorted in descending order
        TreeSet<Integer> treeSet = new TreeSet<>((o1, o2) -> {
            if (o2 > o1 || o2 == o1) {
                return 1; // puts higher or equal elements first
            } else if (o2 < o1) {
                return -1;
            }
 
            return 1;
        });
 
        for (int a : arr) {
            treeSet.add(a);
        }
 
        Iterator<Integer> iterator = treeSet.iterator();
 
        // Retrieve the first K elements
        while (iterator.hasNext() && k > 0) {
            Integer temp = iterator.next();
            System.out.println(temp);
            --k;
        }
    }
}

Conclusion & Complexity Analysis

Using a self-sorting TreeSet with a custom comparator allows us to retrieve the top K elements in O(1) once the tree is built. Each insertion runs in O(log N). While using a heap-based PriorityQueue is also popular, this TreeSet technique offers a clean, set-based alternative. Understanding how custom comparators impact element uniqueness is essential to master Java's collections framework.