Sorting, Comparable, Comparator and Queues

Sorting numbers and strings is easy – they already know their natural order. But how should Java sort students: by marks, by name, by marks and then by name? This lesson shows the two ways to teach Java how to order your objects, plus the queue structures used in schedulers, BFS and "top K" problems.

Comparable: the natural order

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

public class Main {
    public static void main(String[] args) {
        List<Student> list = new ArrayList<>(List.of(
            new Student("Ravi", 72), new Student("Sana", 91), new Student("Om", 85)));
        Collections.sort(list);                  // uses compareTo
        System.out.println(list);
    }
}

class Student implements Comparable<Student> {
    final String name;
    final int marks;

    Student(String name, int marks) { this.name = name; this.marks = marks; }

    @Override
    public int compareTo(Student other) {        // negative / 0 / positive
        return Integer.compare(this.marks, other.marks);
    }

    @Override public String toString() { return name + "(" + marks + ")"; }
}

[Ravi(72), Om(85), Sana(91)]

compareTo returns a negative number if this comes first, zero if equal, positive if it comes after. Use Integer.compare, not this.marks - other.marks, which can overflow for large values.

Comparator: any order you like

A class has one natural order, but you often need several. A Comparator is a separate object (usually a lambda) that defines an order:

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

public class Main {
    record Employee(String name, String dept, double salary) {}

    public static void main(String[] args) {
        List<Employee> staff = new ArrayList<>(List.of(
            new Employee("Asha", "IT", 85000), new Employee("Ben", "HR", 60000),
            new Employee("Chen", "IT", 92000), new Employee("Dia", "HR", 60000)));

        staff.sort(Comparator.comparing(Employee::name));
        System.out.println(names(staff));
        staff.sort(Comparator.comparingDouble(Employee::salary).reversed());
        System.out.println(names(staff));
        staff.sort(Comparator.comparing(Employee::dept)
                             .thenComparing(Employee::salary, Comparator.reverseOrder())
                             .thenComparing(Employee::name));
        System.out.println(names(staff));
    }

    static List<String> names(List<Employee> list) {
        List<String> out = new ArrayList<>();
        for (Employee e : list) out.add(e.name() + "/" + e.dept() + "/" + (int) e.salary());
        return out;
    }
}

[Asha/IT/85000, Ben/HR/60000, Chen/IT/92000, Dia/HR/60000]
[Chen/IT/92000, Asha/IT/85000, Ben/HR/60000, Dia/HR/60000]
[Ben/HR/60000, Dia/HR/60000, Chen/IT/92000, Asha/IT/85000]

Collections utilities

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

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(List.of(42, 7, 19, 7, 25));
        System.out.println(Collections.max(nums) + " " + Collections.min(nums) + " " + Collections.frequency(nums, 7));
        Collections.sort(nums, Collections.reverseOrder());
        System.out.println(nums);
        Collections.reverse(nums);
        System.out.println(nums);
        Collections.swap(nums, 0, nums.size() - 1);
        System.out.println(nums);
        List<Integer> locked = Collections.unmodifiableList(nums);
        System.out.println(locked.size() + " (read-only view)");
    }
}

42 7 2
[42, 25, 19, 7, 7]
[7, 7, 19, 25, 42]
[42, 7, 19, 25, 7]
5 (read-only view)

Stacks and queues with ArrayDeque

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean balanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) stack.push(c);
            else if (")]}".indexOf(c) >= 0) {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ("([{".indexOf(open) != ")]}".indexOf(c)) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(balanced("{[()()]}") + " " + balanced("([)]"));
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("order-1");
        queue.offer("order-2");
        queue.offer("order-3");
        System.out.println(queue.poll() + " served, waiting " + queue);
    }
}

true false
order-1 served, waiting [order-2, order-3]

As a stack (last in, first out) use push/pop/peek; as a queue (first in, first out) use offer/poll/peek. Avoid the legacy Stack class.

PriorityQueue: always the smallest (or largest) first

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

public class Main {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
        tasks.add(new Task("send report", 3));
        tasks.add(new Task("fix outage", 1));
        tasks.add(new Task("reply email", 2));
        while (!tasks.isEmpty()) System.out.print(tasks.poll().name() + " → ");
        System.out.println("done");

        // Top 3 scores with a min-heap of size 3
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int s : List.of(45, 92, 67, 88, 23, 99, 71)) {
            heap.offer(s);
            if (heap.size() > 3) heap.poll();
        }
        System.out.println("top 3 (smallest first): " + heap.stream().sorted().toList());
    }
}

fix outage → reply email → send report → done
top 3 (smallest first): [88, 92, 99]

A PriorityQueue is a binary heap: offer and poll are O(log n). The "keep a heap of size K" trick solves many top-K interview problems in O(n log K).

Practice

Summary

Interview practice: Java Collections Framework questions.