Priority Queue and iterator

[Arvind Darwin]

So I was playing with priority queue. Here is the code (its loosely based on K&B example).

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

public class PQueue {

    public static void main (String[] args) {
        PriorityQueue<Job> pq = new PriorityQueue<Job>();
        
        int[] a = {1,5,3,7,2,9,4,10};
        
        for(int i: a){
            pq.offer(new Job(i, "Name:"+i));
        }
       
        // Queue created with Descending priority
        System.out.println("\nQueue created with Descending priority");
        System.out.println("----------------------------------------");
        System.out.println("Highest priority: " + pq.peek());
        
        Iterator<Job> it = pq.iterator();
        
        System.out.println("\nIterator");
        while(it.hasNext()){
            Job j = it.next();
            
            System.out.print(j);
        }
        
        System.out.println();
        
        System.out.println("\nPoll");
        for(int i: a){
            System.out.print(pq.poll());
        }
        
        System.out.println();
        
        PriorityQueue<Job> pq2 = new PriorityQueue<Job>(10, new Job.PrioritySort());
        
        for(int i: a){
            pq2.offer(new Job(i, "Name:"+i));
        }

        // Queue created with Ascending priority
        System.out.println("\nQueue created with Ascending priority comparator");
        System.out.println("--------------------------------------------------");
        System.out.println("Highest priority: " + pq2.peek());
        
        it = pq2.iterator();
        
        System.out.println("\nIterator");
        while(it.hasNext()) {
            Job j = it.next();
            
            System.out.print(j);
        }
        
        System.out.println();
        
        System.out.println("\nPoll");
        for(int i: a){
            System.out.print(pq2.poll());
        }
        
        System.out.println();
    }
}

class Job implements Comparable<Job>{

    private int priority;
    private String jobName;
    
    public Job(int priority, String name){
        this.priority = priority;
        this.jobName = name;
    }
    
    public int getPriority(){
        return priority;
    }
    
    public String getJobName(){
        return jobName;
    }
    
    // Descending order
    @Override
    public int compareTo(Job a){        
        return a.getPriority() - this.getPriority();
    }
    
    public String toString (){
        return "[" + this.jobName + "]";
    }
    
    // Ascending order
    static class PrioritySort implements Comparator<Job> {
        public int compare(Job one, Job two){
            return one.getPriority() - two.getPriority();
        }
    }
    
}

The output is:

Queue created with Descending priority
----------------------------------------
Highest priority: [Name:10]

Iterator
[Name:10][Name:9][Name:7][Name:5][Name:2][Name:3][Name:4][Name:1]

Poll
[Name:10][Name:9][Name:7][Name:5][Name:4][Name:3][Name:2][Name:1]

Queue created with Ascending priority comparator
--------------------------------------------------
Highest priority: [Name:1]

Iterator
[Name:1][Name:2][Name:3][Name:7][Name:5][Name:9][Name:4][Name:10]

Poll
[Name:1][Name:2][Name:3][Name:4][Name:5][Name:7][Name:9][Name:10]

My Question is:

When I use iterator to print values it does not print in order of priority, but when I poll() it follows the priority order.

Why? Can someone please explain this behavior? Iterator does not use comparable or comparator interface?

Thanks.

[Norbert Muench]

A short look into the Javadoc for the PriorityQueue answers your question:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

[Helen Ma]

The items that are put in a priority queue are sorted by heap sort algorithm. Heap sort is to put items in a binary tree data structure.
The item with the highest priority is put at the root of the tree. The two children has lower priority than the root and so on.
So, when you poll an item, you remove the item in the root of the tree. One of its children move up to the root and so on.

[Helen Ma]

For more information, you can take a look at the post named "Mystic with PriorityQueue" posted on February, 04, 2012.

Correct anything if the answer is wrong in the post thread.

[Arvind Darwin]

Got it! Thanks for the explanation.