19 Java - Priority Queue, Compartor vs Comparble

Chetan DattaChetan Datta
7 min read

Table of contents

Priority Queue

  • Queue is an interface, child of Collection interface.

  • Generally Queue follows FIFO approach, but there are exceptions like PriorityQueue

  • Supports all the methods available in Collection + some other methods mentioned below

Methods

add()

  • Insert the element into the Queue.

  • True if Inserting is Successful and Exception if Insertion fails

  • Null Elememt insertion is not allowed will throw (NPE)

offer()

  • Insert the element into the queue.

  • True if insertion is Successful and False if Insertion fails

  • Null element insertion is not allowed will throw (NPE)

remove()

  • Retrieves and removes the head of the queue.

  • Returns Exception (NoSuchElementException) if Queue is Empty.

poll()

  • Retrieves and Removes the head of the queue.

  • Returns null if Queue is Empty

peek()

  • Retrieves the value present at the head of the queue but do not removes it.

  • Returns null if Queue is empty.

element()

  • Retrieves the value present at the head of the queue but do not removes it.

  • Returns an Exception (NoSuchElementException) if Queue is Empty.

  • Its of 2 types, Minimum Priority Queue and Maximum Priority Queue.

  • It is based on priority Heap (Min Heap and Max Heap)

  • Elements are ordered according to either Natural Ordering (by default) or by Comparator provided

public class Main {
    public static void main(String[] args) {

        //min priority queue, used to solve problems of min heap.
        PriorityQueue<Integer> minPQ = new PriorityQueue<>();
        minPQ.add(5);
        minPQ.add(2);
        minPQ.add(8);
        minPQ.add(1);

        //lets print all the values
        minPQ.forEach((Integer val) -> System.out.println(val));

        //remove top element from the PQ and print
        while (!minPQ.isEmpty()){
            int val = minPQ.poll();
            System.out.println("remove from top: "+ val);
        }
    }
}

1
2
8
5
remove from top: 1
remove from top: 2
remove from top: 5
remove from top: 8

Explanation

Insertion: If x is the value which we want to insert into the heap then based on the root value it's insertion is decided. If x<root then we insert on the left side of root and viceversa. Similarly we compare x with child nodes and at last we insert it.

Heapify: After the insertion we do heapify. In this process root value should be smaller than the child nodes if not we swap the root with smallest child node value.

Max Priority Queue

public class Main {
    public static void main(String[] args) {

        //min priority queue, used to solve problems of min heap.
        PriorityQueue<Integer> minPQ = new PriorityQueue<>((Integer a, Integer b) -> b-a);
        minPQ.add(5);
        minPQ.add(2);
        minPQ.add(8);
        minPQ.add(1);

        //lets print all the values
        minPQ.forEach((Integer val) -> System.out.println(val));

        //remove top element from the PQ and print
        while (!minPQ.isEmpty()){
            int val = minPQ.poll();
            System.out.println("remove from top: "+ val);
        }
    }
}


8
2
5
1
remove from top: 8
remove from top: 5
remove from top: 2
remove from top: 1

Time Complexity:

Add and Offer: O(logn)

Peak: O(1)

Poll and Remove head element: O(logn)

Remove arbitrary element: O(n)

Sorting Issues

Primitive collection sorting

If we want to sort the array based on a certain parameter, it is difficult with default sorting.

public class Main {
    public static void main(String[] args) {
        int[] array = {1,2,3,4};
        Arrays.sort(array);
    }
}

Object Collection Sorting

public class Car {
    String carName;
    String carType;

    public Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }
}

public class Main {
    public static void main(String[] args) {
        Car[] carArray = new Car[3];
        carArray[0] = new Car("SUV","petrol");
        carArray[1] = new Car("Sedan", "diesel");
        carArray[2] = new Car("HatchBack", "CNG");

        Arrays.sort(carArray);
    }
}

/*

Exception in thread "main" java.lang.ClassCastException: class learn.Exception.Car cannot be cast to class java.lang.Comparable (learn.Exception.Car is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
    at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
    at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
    at java.base/java.util.Arrays.sort(Arrays.java:1041)
    at learn.Exception.Main.main(Main.java:14)

*/

How to sort the Object Array?

Comparator and Comparable both provides a way to sort the collection of objects.

Comparator

int compare(T obj1, T obj2)
  • Sorting algorithm uses this compare method of Comparator to compare 2 variables and decide whether to swap the variables or not.

method returns

  • 1: if v1 is bigger than v2

  • 0: if v1 and v2 is equals

  • -1: if v1 is smaller than v2

Mostly in algorithm, if this method returns 1, it swaps the values.

Sorting numbers in ascending order

public class Main {
    public static void main(String[] args) {
        Integer a[] = {6,4,1,9,2,11};
        Arrays.sort(a, (Integer val1, Integer val2)-> val1 - val2);

        for (int v : a){
            System.out.println(v);
        }
    }
}

1
2
4
6
9
11

Sorting numbers in descending order

public class Main {
    public static void main(String[] args) {
        Integer a[] = {6,4,1,9,2,11};
        Arrays.sort(a, (Integer val1, Integer val2)-> val2 - val1);

        for (int v : a){
            System.out.println(v);
        }
    }
}

11
9
6
4
2
1

Sorting objects in descending order (car type)

public class Car {
    String carName;
    String carType;

    public Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }

    public String getCarName() {
        return carName;
    }

    public String getCarType() {
        return carType;
    }
}

public class Main {
    public static void main(String[] args) {
        Car[] carArray = new Car[3];
        carArray[0] = new Car("SUV","petrol");
        carArray[1] = new Car("Sedan", "diesel");
        carArray[2] = new Car("HatchBack", "CNG");

        Arrays.sort(carArray, (Car obj1, Car obj2) -> obj2.getCarType().compareTo(obj1.getCarType()));

        for (Car car: carArray){
            System.out.println(car.getCarName() + ".."+car.getCarType());
        }
    }
}

/*
SUV..petrol
Sedan..diesel
HatchBack..CNG
*/

Sorting objects in ascending order (car name)

public class Main {
    public static void main(String[] args) {
        Car[] carArray = new Car[3];
        carArray[0] = new Car("SUV","petrol");
        carArray[1] = new Car("Sedan", "diesel");
        carArray[2] = new Car("HatchBack", "CNG");

        Arrays.sort(carArray, (Car obj1, Car obj2) -> obj1.getCarName().compareTo(obj2.getCarName()));

        for (Car car: carArray){
            System.out.println(car.getCarName() + ".."+car.getCarType());
        }
    }
}
/*
HatchBack..CNG
SUV..petrol
Sedan..diesel
*/

Sorting Collection of objects

public class Main {
    public static void main(String[] args) {
        List<Car> cars = new ArrayList<>();
        cars.add(new Car("SUV","petrol"));
        cars.add(new Car("Sedan", "diesel"));
        cars.add(new Car("HatchBack", "CNG"));

        Collections.sort(cars, (Car obj1, Car obj2) -> obj2.getCarName().compareTo(obj1.getCarName()));

        cars.forEach((Car carObj) -> System.out.println(carObj.getCarName()+ ".."+carObj.getCarType()));
    }
}
/*
Sedan..diesel
SUV..petrol
HatchBack..CNG
*/

Custom Comparator

public class CarNameComparator implements Comparator<Car> {

    @Override
    public int compare(Car o1, Car o2) {
        return o2.getCarName().compareTo(o1.getCarName());
    }
}

public class Main {
    public static void main(String[] args) {
        List<Car> cars = new ArrayList<>();
        cars.add(new Car("SUV","petrol"));
        cars.add(new Car("Sedan", "diesel"));
        cars.add(new Car("HatchBack", "CNG"));

        Collections.sort(cars, new CarNameComparator());

        cars.forEach((Car carObj) -> System.out.println(carObj.getCarName()+ ".."+carObj.getCarType()));
    }
}
/*
Sedan..diesel
SUV..petrol
HatchBack..CNG
*/

Comparable

int compareTo(T obj2);

  • Sorting algorithm uses this compareTo method of Comparator to compare 2 variables and decide whether to swap the variables or not.

  • To use the Comparable interface for sorting, the objects must implement this interface. No additional parameters are required for sorting. The sorting algorithm internally invokes the compareTo method of the objects.

  • When examining the sorting process more closely, we see that it directly calls the compareTo method of the objects.

Example

public class Car implements Comparable<Car>{
    String carName;
    String carType;

    public Car(String carName, String carType) {
        this.carName = carName;
        this.carType = carType;
    }

    public String getCarName() {
        return carName;
    }

    public String getCarType() {
        return carType;
    }

    @Override
    public int compareTo(Car o) {
        return this.getCarName().compareTo(o.getCarName());
    }
}

public class Main {
    public static void main(String[] args) {
        List<Car> cars = new ArrayList<>();
        cars.add(new Car("SUV","petrol"));
        cars.add(new Car("Sedan", "diesel"));
        cars.add(new Car("HatchBack", "CNG"));

        Collections.sort(cars);
        cars.forEach((Car carObj) -> System.out.println(carObj.getCarName()+ ".."+carObj.getCarType()));
    }
}

Note

  • Collections.sort() internally calls the Arrays.sort().

  • If a comparator is not supplied, the compareTo method of the object is called internally.

  • Comparator and Comparable are used to determine whether to swap the objects o1 and o2.

  • A comparator is more flexible than Comparable because the Comparable method is inside the object, making it a fixed implementation for the entire class.

  • All the primitive data types Integer, String ..etc implement the Comparable interface.

0
Subscribe to my newsletter

Read articles from Chetan Datta directly inside your inbox. Subscribe to the newsletter, and don't miss out.

priority queuejava comparatorcomparablecomparable vs comparatorJava

Written by

Chetan Datta
Chetan Datta

I'm someone deeply engrossed in the world of software developement, and I find joy in sharing my thoughts and insights on various topics. You can explore my exclusive content here, where I meticulously document all things tech-related that spark my curiosity. Stay connected for my latest discoveries and observations.