The output of PriorityQueue varies for sorted and unsorted array

I am implementing Priority Queue and I am not able to understand why are there different outputs for sorted and unsorted array. The code and the output is shown below :

Sorted Array

import java.io.*;
import java.util.*;
class Test {
    public static void main(String args[] ) throws Exception {
       PriorityQueue<Integer> pq=new PriorityQueue<>();
       int[] a={0,1,2,3,4,5,6,7,8};
       for (int x:a ) {
        pq.add(x);
       }
       Iterator itr=pq.iterator();
       while(itr.hasNext()){
        System.out.print(itr.next()+" ");
       }
       System.out.println();
    }
}

Output : 0 1 2 3 4 5 6 7 8

Unsorted Array

import java.io.*;
import java.util.*;
class Test {
    public static void main(String args[] ) throws Exception {
       PriorityQueue<Integer> pq=new PriorityQueue<>();
       int[] a={4,3,6,2,1,5};
       for (int x:a ) {
        pq.add(x);
       }
       Iterator itr=pq.iterator();
       while(itr.hasNext()){
        System.out.print(itr.next()+" ");
       }
       System.out.println();
    }
}

Output : 1 2 5 4 3 6

Can anyone explain me why is there a difference between the outputs for the two scenarios?

Solution

PriorityQueue in Java is implemented as a binary heap. The order of items in a binary heap depends on the order in which they are inserted. For example, inserting the items [1, 2, 3, 4] in order would give you the heap:

      1
    2   3
  4

But if you were to insert in the order [1, 3, 4, 2], then your heap would be:

      1
    3   2
  4

Remember, a binary heap isn't a sorted data structure. It's ordered in such a way that the smallest item (in the case of a min-heap) is always at the root, and child nodes are larger than their parents. But there are many possible heap orderings for a given group of items.

Update

You asked, "how would {4,3,6,2,1,5} be ordered in the heap?" Let's walk through it.

Insert 4: {4}
Insert 3: {3,4}
Insert 6: {3,4,6}
Insert 2: 2 is added to the end of the heap: {3,4,6,2}, and then sifted up. First it's swapped with its parent to make {3,2,6,4}, and then swapped again with the root to create {2,3,6,4}.
Insert 1: Add to the end of the heap {2,3,6,4,1}. Swap with parent {2,1,6,4,3}, then swap with root to create {1,2,6,4,3}.
Insert 5: Add to the end of the heap {1,2,6,4,3,5}. Swap with parent to create {1,2,5,4,3,6}.