Why does PriorityQueue.toString return the wrong element order? [duplicate]

You need to poll the items from the PriorityQueue one by one. toString doesn't do that.

So instead of your System.out.println(queue); do this:

while(!queue.isEmpty()) {
   System.out.println(queue.poll());
}

The reason is that the PriorityQueue is never completely sorted internally, lookup how a heap works for more detail. Polling items from it fixes the heap during the calls, thus it should output the elements in sorted order.

The System.out.println(queue) is printing the queue unsorted. If you want to print the queue real order follow the below code which use poll to get the elements from the queue top to bottom:

TreeNodeHuffman tn = null;
    do{
        tn = queue.poll();
        if(tn!=null){
            System.out.print(tn.key+",");
        }
    }while(tn != null);

and you shall see this output as expected:

z,q,x,j,k,v,b,p,y,g,f,w,m,u,c,l,d,r,h,s,a,i,o,a,t,e,