How to iterate over a PriorityQueue?

by

You can’t traverse a Priority Queue in that order because of the underlying implementation (I think it’s min-heap in Java).

It’s not a sorted array, so that you can just go from one element to the one with the lesser priority.

Peeking (read the top element heap in the heap) is constant time O(1) because it looks at the smallest element.

To get the second next one you must dequeue the smallest top element, that’s how it works.
Dequeing (re-heapify = O(log n) time) isn’t just a matter of taking that element out, the underlying structure rearranges itself in order to bring the element with the least priority first.

Also, to go through the entire priority queue to read all items in the sorted order, it is an O(n log(n)) operation.
So you may as well just grab all the elements in the queue and sort them (also O(n log (n)) )and then you can go through them as you wish. The only disadvantage is that you’re holding an extra-copy of the queue.

Nonetheless, if you need to traverse the data in this way a priority queue may not be the right data structure for your needs.

More Related Contents:

  1. Ways to iterate over a list in Java
  2. How Iterator’s remove method actually remove an object
  3. How to flatten all items from a nested Java Collection into a single List?
  4. What is the value of the variable result after the following code is executed?
  5. How to end while loop in Java
  6. How to loop through a HashMap in JSP?
  7. How to convert comma-separated String to List?
  8. Getting an element from a Set
  9. Why there is no ConcurrentHashSet against ConcurrentHashMap
  10. Assert equals between 2 Lists in Junit
  11. Java Immutable Collections
  12. How do I keep the iteration order of a List when using Collections.toMap() on a stream?
  13. What is the most efficient Java Collections library? [closed]
  14. How to convert a Java object (bean) to key-value pairs (and vice versa)?
  15. How can I get a List from some class properties with Java 8 Stream?
  16. Binding a list in @RequestParam
  17. What is the time complexity performance of HashSet.contains() in Java?
  18. Iterating over Java collections in Scala
  19. Is it faster to add to a collection then sort it, or add to a sorted collection?
  20. Why does LinkedHashSet extend HashSet and implement Set
  21. Java: how to convert HashMap to array
  22. The easiest way to transform collection to array?
  23. How to use Collections.sort() in Java?
  24. Comparing two hashmaps for equal values and same key sets?
  25. When should I return the Interface and when the concrete class?
  26. Storing different types of elements in a List in Java
  27. Are they any decent on-disk implementations of Java’s Map?
  28. Hashmap implementation to count the occurrences of each character
  29. Perform operation on n random distinct elements from Collection using Streams API
  30. Simple Java PriorityQueue error

Leave a Comment