Why does my PriorityBlockingQueue in Java not sort properly?

Question

For some reason when I add to the priority queue, it doesn't sort my strings entirely alphabetically and I can't see why.

This is the code which adds to the PriorityBlockingQueue:

String toAdd = String.format("%s/%s", directory, s);
outputData.add(toAdd);

But I get not entirely sorted output (only first few lines but you can see it's not sorted):

../StartingTree/files/abknl/apfmpohgyh/a.class
../StartingTree/files/abknl/apfmpohgyh/a.java
../StartingTree/files/abknl/aqybc/aeph.java
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.class
../StartingTree/files/abknl/bbxudleuf/jlffhq/y/xwjj/dyetqhsch/bpg.class
../StartingTree/files/abknl/bbxudleuf/mxb/fe/ndmg/axapxuco.html
../StartingTree/files/abknl/aqybc/atyuojdu.txt

And this is the real (first part) of sorted output from the expected-output file:

../StartingTree/files/abknl/apfmpohgyh/a.class
../StartingTree/files/abknl/apfmpohgyh/a.java
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.class
../StartingTree/files/abknl/apfmpohgyh/bnjuxxdi.java
../StartingTree/files/abknl/apfmpohgyh/bsqsq.class
../StartingTree/files/abknl/apfmpohgyh/bsqsq.java
../StartingTree/files/abknl/apfmpohgyh/ds.class
../StartingTree/files/abknl/apfmpohgyh/ds.java

possible duplicate of Why do I get the following result?

Raedwald
– Raedwald

2014-03-01 12:33:52 +00:00
Commented Mar 1, 2014 at 12:33 — Raedwald
– Raedwald, Commented Mar 1, 2014 at 12:33

amit · Accepted Answer · 2012-11-13 23:08:18Z

7

I suspect you are trying to iterate the PriorityBlockingQueue and print the elements.

Note that a Priority Queue data structure (AKA heap) does not guarantee ordering - it guarantees that the head is minimal, but no order guarantee on any of the following nodes.

If you want your data maintained sorted - I suggest using something like ConcurrentSkipListSet (Note however it is a set - thus it does not allow duplicate entrees), or maintaining a sorted List.

If you want to get the sorted elements using a PriorityBlockingQueue - you should iteratively delete the head and output the new head - until the priority queue is exhausted. It will guarantee an ordered output.

answered Nov 13, 2012 at 23:08

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Geesh_SO Over a year ago

Oh, I had in my head that every element would be perfectly sorted, I had no idea it was only the head which was minimal. I'll just use another structure and then write my own code for insertion :) Any recommendations on data structures in multi-thread programs (i.e. where more than one thread might try to access my data concurrently) ?

assylias Over a year ago

+1 Or (cf javadoc): "If you need ordered traversal, consider using Arrays.sort(pq.toArray())."

amit Over a year ago

@Geesh_SO: If you don't have duplicate elements, I suggest using a ConcurrentSkipListSet. See new version of the answer.

Collectives™ on Stack Overflow

Why does my PriorityBlockingQueue in Java not sort properly?

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related