kaksha.dev

---

Comparable vs Comparator in Java

1. Comparable Interface

• Purpose: Used to define the natural ordering of objects in a collection.
• Method to Implement: Implements the compareTo(T o) method.
• Where to Use: When the class itself defines how its objects should be compared.
• Modification: Affects the class directly.
• Syntax:

  public class MyClass implements Comparable<MyClass> {
      @Override
      public int compareTo(MyClass other) {
          // Return negative if 'this' < 'other', zero if equal, positive if greater.
          return this.property - other.property;
      }
  }
  

Example:

import java.util.*;

class Student implements Comparable<Student> {
    int id;
    String name;

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

    @Override
    public int compareTo(Student other) {
        return this.id - other.id; // Sort by ID
    }

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

public class ComparableExample {
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
                new Student(3, "Alice"),
                new Student(1, "Bob"),
                new Student(2, "Charlie")
        );

        Collections.sort(students); // Sort using natural ordering
        System.out.println(students); // Output: [1: Bob, 2: Charlie, 3: Alice]
    }
}

---

2. Comparator Interface

• Purpose: Used to define a custom ordering of objects.
• Method to Implement: Implements the compare(T o1, T o2) method.
• Where to Use: When the ordering logic is external to the class.
• Multiple Comparisons: Can define multiple comparison strategies.
• Syntax:

  Comparator<MyClass> comparator = (o1, o2) -> o1.property - o2.property;
  

Example:

import java.util.*;

class Student {
    int id;
    String name;

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

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

public class ComparatorExample {
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
                new Student(3, "Alice"),
                new Student(1, "Bob"),
                new Student(2, "Charlie")
        );

        // Sort by name using Comparator
        students.sort(Comparator.comparing(student -> student.name));
        System.out.println(students); // Output: [3: Alice, 1: Bob, 2: Charlie]
    }
}

---

Priority Queue (Min Heap and Max Heap) in Java

PriorityQueue Basics

• Default Behavior: Min-Heap (smallest element at the top).
• Customization: Use a custom Comparator for a Max-Heap or other orders.
• Time Complexity:
  • add() / offer(): (O(\log n))
  • poll(): (O(\log n))
  • peek(): (O(1))

Min-Heap Example (Default Behavior):

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.add(5);
        minHeap.add(1);
        minHeap.add(3);

        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll()); // Output: 1, 3, 5
        }
    }
}

Max-Heap Example:

import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

        maxHeap.add(5);
        maxHeap.add(1);
        maxHeap.add(3);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // Output: 5, 3, 1
        }
    }
}

---

Using Comparable and Comparator in PriorityQueue

1. Using Comparable:

import java.util.PriorityQueue;

class Student implements Comparable<Student> {
    int id;
    String name;

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

    @Override
    public int compareTo(Student other) {
        return this.id - other.id; // Natural ordering by ID
    }

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

public class PQWithComparable {
    public static void main(String[] args) {
        PriorityQueue<Student> pq = new PriorityQueue<>();

        pq.add(new Student(3, "Alice"));
        pq.add(new Student(1, "Bob"));
        pq.add(new Student(2, "Charlie"));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Output:

1: Bob
2: Charlie
3: Alice

---

2. Using Comparator (Custom Ordering):

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

class Student {
    int id;
    String name;

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

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

public class PQWithComparator {
    public static void main(String[] args) {
        // Custom comparator to sort by name
        PriorityQueue<Student> pq = new PriorityQueue<>(Comparator.comparing(student -> student.name));

        pq.add(new Student(3, "Alice"));
        pq.add(new Student(1, "Bob"));
        pq.add(new Student(2, "Charlie"));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Output:

3: Alice
1: Bob
2: Charlie

---

3. Using Lambda Directly in PriorityQueue:

import java.util.PriorityQueue;

class Student {
    int id;
    String name;

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

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

public class PQWithLambda {
    public static void main(String[] args) {
        // Max-Heap by ID using Lambda
        PriorityQueue<Student> pq = new PriorityQueue<>((a, b) -> b.id - a.id);

        pq.add(new Student(3, "Alice"));
        pq.add(new Student(1, "Bob"));
        pq.add(new Student(2, "Charlie"));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Output:

3: Alice
2: Charlie
1: Bob

---

Key Points

• Use Comparable for natural ordering directly within the class.
• Use Comparator for custom ordering, which can be applied dynamically.
• PriorityQueue is by default a Min-Heap; for a Max-Heap, provide a custom comparator or lambda expression.
• Lambdas simplify custom comparisons and make code concise.