Priority Queue in Java

'Priority Queue' is a data structure similar to Queue, but pulls/pops out the first element with top priority first (FPIFO, for convenience), whereas Queue is just 'First In First Out' (FIFO). This data structure can be used in a variety of applications like Scheduling, Bandwidth Management, Discrete Event Simulation, etc.

I was just coding for fun and for brushing up my skills on algorithms and coded a few examples, as listed below. As shown in the examples, I used the Java's PriorityQueue implementation in the util package.

In the below example, the priority queue is fed with Integer numbers and the priority is determined by checking if the number is a least prime or not.
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * @author Babji P, Chetty
 */
public class PQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>(10, new Comparator<Integer>() {

            public int compare(Integer int1, Integer int2) {
                boolean flag1 = isPrime(int1);
                boolean flag2 = isPrime(int2);
                
                if (flag1 == flag2){
                    return int1.compareTo(int2);
                } else if (flag1) {
                    return -1;
                } else if(flag2) {
                    return 1;
                }
                
                return 0;
            }
        });

        pQueue.add(10);
        pQueue.add(8);
        pQueue.add(6);
        pQueue.add(4);
        pQueue.add(2);
        pQueue.add(9);
        pQueue.add(7);
        pQueue.add(5);
        pQueue.add(3);
        pQueue.add(1);

        while(true) {
            Integer head = pQueue.poll();
            if(head == null) {
                break;
            }
            
            System.out.print(head + "  <-- ");
        }
    }
    
    /**
     * 
     * @param n
     * @return 
     */
    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        long m = (long) Math.sqrt(n);

        for (long i = 3; i  <= m; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }
}

The output for the above example is:
2 <-- 3 <-- 5 <-- 7 <-- 1 <-- 4 <-- 6 <-- 8 <-- 9 <-- 10 <--
As you see, prime numbers appear before other numbers.

The below example is more of a real world example, where the order of patients to be treated by a doctor can be determined by checking if it's a emergency case or not.

Below is the code for 'Patient' class:
/**
 *
 * @author Babji P, Chetty
 */
public class Patient {
    private int id;
    private String name;
    private boolean emergencyCase;
    
    public Patient(int id, String name, boolean emergencyCase) {
        this.id = id;
        this.name = name;
        this.emergencyCase = emergencyCase;
    }

    /**
     * @return the id
     */
    public int getId() {
        return id;
    }

    /**
     * @param id the id to set
     */
    public void setId(int id) {
        this.id = id;
    }
    
    /**
     * @return the name
     */
    public String getName() {
        return name;
    }

    /**
     * @param name the name to set
     */
    public void setName(String name) {
        this.name = name;
    }

    /**
     * @return the emergencyCase
     */
    public boolean isEmergencyCase() {
        return emergencyCase;
    }

    /**
     * @param emergencyCase the emergencyCase to set
     */
    public void setEmergencyCase(boolean emergencyCase) {
        this.emergencyCase = emergencyCase;
    }
}


And below is the code for testing Patient priority queue:

import com.chetty.algos.data.Patient;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 *
 * @author Babji Prashanth, Chetty
 */
public class PQueueTest {
    public static void main(String[] args) {
        PriorityQueue<Patient> patientQueue = new PriorityQueue<Patient>(10, new Comparator() {
            public int compare(Patient patient1, Patient patient2) {
                return (patient1.isEmergencyCase() == patient2.isEmergencyCase()) ? (Integer.valueOf(patient1.getId()).compareTo(patient2.getId()))
                                                                                  : (patient1.isEmergencyCase() ? -1 : 1);
            }
        });
        
        patientQueue.add(new Patient(1, "Patient1", false));
        patientQueue.add(new Patient(2, "Patient2", false));
        patientQueue.add(new Patient(3, "Patient3", true));
        patientQueue.add(new Patient(4, "Patient4", false));
        patientQueue.add(new Patient(5, "Patient5", true));
        
        System.out.println();
        System.out.print("Doctor's waiting for patients  : ");
        while(true) {
            Patient currentPatient = patientQueue.poll();
            if(currentPatient == null) {
                break;
            }
            
            System.out.print(currentPatient.getName() + " <-- ");
        }
        System.out.println();
    }
}


The output for the above example is:
Doctor's waiting for patients : Patient3 <-- Patient5 <-- Patient1 <-- Patient2 <-- Patient4 <--
As you see, patients who need to be treated immediately (emergency cases) appear before other patients.

2 comments:

  1. new Comparator() should be
    new Comparator()


    Thanks so much for your example...

    ReplyDelete
    Replies
    1. Nicely explained. Good job.

      I have a question. Why do we always say Comparable interface as natural ordering where as we can implement our own logic like you did in comparator ?

      Thanks in advacne!

      Delete

Note: Only a member of this blog may post a comment.