Problem with priority Queue

[Santhosh Gowd]

I am using PriorityQueue but it is not giving me exact sorting. This is my code:

class Compare2DArray implements Comparator<int[]> {
public int compare(int a[], int b[]) {
    for (int i = 0; i < a.length && i < b.length; i++)
        if (a[i] != b[i])
            return a[i] - b[i];
    return a.length - b.length;
}
}

public class MyClass{
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int numberOfInputs= scan.nextInt();
        PriorityQueue<int[]> inputsList = new PriorityQueue<int[]>(numberOfInputs,new Compare2DArray());
        for (int i = 0; i < numberOfInputs; i++) {
            int[] input = new int[2];
            input[0] = scan.nextInt();
            input[1] = scan.nextInt();
            inputsList.add(input);

        }
    }

But this is sorting this queue of arrays

2 2
1 1
4 3
10 1
2 1

as

1 1
2 1
4 3
10 1
2 2

instead of

1 1
2 1
2 2
4 3
10 1

The same comparator works fine over List sorting. I am not getting whats wrong with PriorityQueue.

[Stephan van Hulst]

I am assuming you're printing the elements using an enhanced for loop. Do you know how the enhanced 'for' works?

[Santhosh Gowd]

The problem is while storing into the priorityqueue, not while printing. I am assuming that while storing into the queue, it stores in a sorted manner.

[Stephan van Hulst]

Well, how do you know how the items are stored?

[Santhosh Gowd]

JavaDoc says about PriorityQueue:
[javadoc]
public class PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

An unbounded priority queue based on a priority heap. "The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used". A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException). [/javadoc]

Is my constructor wrong or my assumption about Queue construction is wrong?

[Stephan van Hulst]

No, the way you're retrieving data from the queue is wrong. I already told you that you're accessing the elements from the queue using an enhanced for loop, and I asked you whether you know how the enhanced for loop works.

[Santhosh Gowd]

I have modified the code like this to use enhanced for loop:

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

class Compare2DArray implements Comparator<int[]> {
	public int compare(int a[], int b[]) {
		for (int i = 0; i < a.length && i < b.length; i++)
			if (a[i] != b[i])
				return a[i] - b[i];
		return a.length - b.length;
	}
}


public class Solution {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int testCases = scan.nextInt();
		PriorityQueue<int[]> inputsList = new PriorityQueue<int[]>(testCases,new Compare2DArray());
		for (int i = 0; i < testCases; i++) {
			int[] input = new int[2];
			input[0] = scan.nextInt();
			input[1] = scan.nextInt();
			inputsList.add(input);
			//findMaxOverShoot(inputsList, i+1);			
		}
		for(int[] a:inputsList){
			System.out.println(a[0]+" "+a[1]);
			
			}
	}

Still the output is same. How does the enhanced for loop works? Previously i was using iterator.

[Rob Spoor]

From the same Javadoc page:

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

The same is true for both toArray methods. The only methods that will respect the order are peek() and poll().