10 Replies Latest reply: Jul 29, 2008 11:00 AM by 807589 RSS

    Why does an Iterator of PriorityQueue not iterate in sorted order?

    807589
      hi, I'm studying toward the SCJP exam, so I don't have much pragmatic realworld experience with the Collection classes. Most of it seem well thought out, but the following I cannot see any meaning to:

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

      What's the thinking behind the decision of this design? Why will an Iterator of an otherwise sorted PriorityQueue will not iterate in sorted order?

      It has ramifications for other methods that base themselves on the iterator, like toArray (won't create an array with elements in the same order as the PriorityQueue) and toString (won't return a string with elements in the same order as they are in the PriorityQueue). (Took me ages to source the problem back to the iterator, thinking that the error had to be in the logic of my Comparators)

      Other collections have Iterators that returns things in the same order as they are in the collection: I can call toString or toArray on an ArrayList and it will return elements in order.

      Using Arrays.sort(pq.toArray()) as the API suggest, looks fishy to me, as I loose any parameterised typing there might have been associated with the PriorityQueue - alas, It'll force me to mix generic and non-generic code.

      Can anyone enlighten me on this design? When is it GOOD to have iterators that return otherwise sorted collections in whatever order they like?

      Edited by: krzn on Jul 29, 2008 12:50 PM
        • 1. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
          JoachimSauer
          One possible reason: A priority queue may easily be implemented as a Heap. It's very fast/easy to get the highest/lowest value of a heap and to insert elements into it. But it's not fast to get a Iterator to return all elements in sorted order.

          And since the design goal of a priority queue is fast updates and fast poll()s using a Heap is a natural choice. If you need the entire Collection to be sorted, then the PriorityQueue is not the data structure of choice.
          • 2. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
            795426
            PriorityQueue is a balanced binary heap backed by an Object[]. This makes iterating in order relatively simple as long as you don't allow modifications to the heap during iteration. Unfortunately, PriorityQueue's iterator allows you to mess with the heap during iteration, which under certain circumstances will need to re-heapify the array, potentially moving unseen elements to the part of the array you've already looked at.

            If you have the JDK, you should have a src.zip file in JDK_HOME. That contains the source for the standard libraries, including PriorityQueue. Go take a look at it.
            • 3. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
              795426
              JoachimSauer wrote:
              But it's not fast to get a Iterator to return all elements in sorted order.
              Er, yes it is. Ignore this.

              Edited by: DeltaGeek on Jul 29, 2008 9:16 AM
              • 4. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
                JoachimSauer
                DeltaGeek wrote:
                JoachimSauer wrote:
                But it's not fast to get a Iterator to return all elements in sorted order.
                Er, yes it is. Ignore this.
                Oops ... must have mixed up my data structures here ... I wonder with what I mixed it up ...
                • 5. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
                  807589
                  >
                  PriorityQueue is a balanced binary heap backed by an Object[]. This makes iterating in order relatively simple as long as you don't allow modifications to the heap during iteration.
                  >

                  It's been a long time since I took Data Structures, but I believe that you can satisfy the heap property without a total ordering.

                  Edit: Knuth, vol 3, 1st ed, p 144 shows a heap that does not have a total ordering. And in the page before, he describes why that can happen, in terms of a tournament ranking.
                  • 6. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
                    807589
                    krzn wrote:
                    hi, I'm studying toward the SCJP exam, so I don't have much pragmatic realworld experience with the Collection classes.
                    Can I just get this in to get it over with?

                    :rollseyes:

                    thanks
                    • 7. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
                      JoachimSauer
                      kdgregory wrote:
                      It's been a long time since I took Data Structures, but I believe that you can satisfy the heap property without a total ordering.

                      Edit: Knuth, vol 3, 1st ed, p 144 shows a heap that does not have a total ordering. And in the page before, he describes why that can happen, in terms of a tournament ranking.
                      Nice, so I wasn't completely off. Good to know ;-)
                      • 8. Thanks for your answers
                        807589
                        DeltaGeek, JoachimSauer & kdgregory: thank you so much for a very very thorough answer to my question. Reading the code behind the code and citing Knuth, aha, yes. I cant help thinking of the closing scene of The Matrix 1 where the code behind the 'real' world is revealed. Thanks a lot guys, you are the Neo's of this forum.

                        DrLaszloJamf: You have a nice day too.
                        • 9. Re: Thanks for your answers
                          807589
                          krzn wrote:
                          DeltaGeek, JoachimSauer & kdgregory: thank you so much for a very very thorough answer to my question. Reading the code behind the code and citing Knuth, aha, yes. I cant help thinking of the closing scene of The Matrix 1 where the code behind the 'real' world is revealed. Thanks a lot guys, you are the Neo's of this forum.

                          DrLaszloJamf: You have a nice day too.
                          Good luck getting the latest dumps.
                          • 10. Re: Why does an Iterator of PriorityQueue not iterate in sorted order?
                            795426
                            JoachimSauer wrote:
                            DeltaGeek wrote:
                            JoachimSauer wrote:
                            But it's not fast to get a Iterator to return all elements in sorted order.
                            Er, yes it is. Ignore this.
                            Oops ... must have mixed up my data structures here ... I wonder with what I mixed it up ...
                            Nothing, I should have written that edit better. It's not simple or fast to do it, and it basically amounts to what the javadocs tell you to do :)