Java Priority Queue Rearranging Itself After Poll Method is Called

Question

I have a class Student which implements Comparable as shown below because I want to put objects of Student in a priority queue and have students who have an earlier registration date to have a higher priority.

public class Student implements Comparable{
    private String fullName;
    private Date registrationDate;

public Student(String fullname){
    this.fullName = fullName;
}



public String getFullName() {
    return fullName;
}

public void setFullName(String fullName) {
    this.fullName = fullName;
}

public Date getRegistrationDate() {
        return registrationDate;
    }
    public void setRegistrationDate(Date registrationDate) {
        this.registrationDate = registrationDate;
    }

@Override
    public int compareTo(Object obj) {
        Student student = (Student) obj;

        if(getRegistrationDate().before(student.getRegistrationDate())){
            return 1;
        }else if(getRegistrationDate().after(student.getRegistrationDate())){
            return -1;
        }
        return 0;
    }
}

In the main method, I am creating objects of students, setting a registration date and putting them in a priority queue

public class School {

    public static void main(String args[]) {

        //list of students
        Student student1 = new Student("John Doe");
        Date dateStudent1Joined = new GregorianCalendar(2014, Calendar.JULY, 1).getTime();
        student1.setRegistrationDate(dateStudent1Joined);

        Student student2 = new Student("Mary Penn");
        Date dateStudent2Joined = new GregorianCalendar(2014, Calendar.JULY, 2).getTime();
        student2.setRegistrationDate(dateStudent2Joined);

        Student student3 = new Student("George Coats");
        Date dateStudent3Joined = new GregorianCalendar(2014, Calendar.JULY, 3).getTime();
        student3.setRegistrationDate(dateStudent3Joined);

        Student student4 = new Student("Tony Case");
        Date dateStudent4Joined = new GregorianCalendar(2014, Calendar.JULY, 4).getTime();
        student4.setRegistrationDate(dateStudent4Joined);

        Student student5 = new Student("Ben Thomas");
        Date dateStudent5Joined = new GregorianCalendar(2014, Calendar.JULY, 5).getTime();
        student5.setRegistrationDate(dateStudent5Joined);

        //create a queue data structure to hold students
        PriorityQueue<Student> studentQueue = new PriorityQueue<Student>();
        //add students to queue
        studentQueue.offer(student1);
        studentQueue.offer(student2);
        studentQueue.offer(student3);
        studentQueue.offer(student4);
        studentQueue.offer(student5);

        //print names of people in queue
        for(Student student : studentQueue){
            String studentName = student.getFullName();
            System.out.println(studentName);
            System.out.println("");

        }

            studentQueue.poll();    

        for(Student student : studentQueue){
            String studentName = student.getFullName();
            System.out.println(studentName);
        }
    }
}

In the first for loop inside School.java, I print out the names of all the students on the queue to ensure they are in the correct priority, which is that student with the earlier registration dates are in front of the queue. The result here is what I expect because John Doe joined first and Ben Thomas joins last.

John Doe
Mary Penn
George Coats
Tony Case
Ben Thomas

However, when I call the poll() method on the priority queue, John Doe is removed but the order of the priority queue no longer makes sense, the output from the second for loop is

Mary Penn
Tony Case
George Coats
Ben Thomas

Mary Penn is in the right position but George Coats should come before Tony Case if the order in the previous priority queue still holds sway, what am I doing wrong here?

Really? No `instanceof` checks in your `compareTo`, yet you perform an unsafe cast? — bcsb1001, Aug 29 '15 at 07:25
I'm not sure what you are talking about but it compiles fine, is that where the problem is? — Jibolash, Aug 29 '15 at 07:30
You cast `obj` to `Student` without an `if (obj instanceof Student)`. — bcsb1001, Aug 29 '15 at 07:36
Please use generics. They exist for more than 10 years. `Student implements Comparable`. — JB Nizet, Aug 29 '15 at 07:36
@bcsb1001 that's perfectly fine, and respects the contract of Comparable. What would he do if obj is not an instance of Student? throw a ClassCastException? That's what the unchecked cast will do anyway. The OP should use generics though. — JB Nizet, Aug 29 '15 at 07:36

score 2 · Answer 1 · edited May 23 '17 at 12:14

2

Look at this. The iteration order of a PriorityQueue is not guaranteed to be sorted. When you call poll() several more times, you will find the order is actually correct.

edited May 23 '17 at 12:14

Community

1
1

answered Aug 29 '15 at 07:34

bcsb1001

2,834
3
24
35

Java Priority Queue Rearranging Itself After Poll Method is Called

1 Answers1