PriorityQueue clarification in Java

Question

In the below code, I want to know the significance of 10 while creating a PrioriyQueue. I know its the initial capacity but will it affect performance??

import java.util.*;

class Test {
    static class PQsort implements Comparator<Integer> { // inverse sort
        public int compare(Integer one, Integer two) {
            return two - one; // unboxing
        }
    }

    public static void main(String[] args) {
        int[] ia = { 1, 5, 3, 7, 6, 9, 8 }; // unordered data
        PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(); // use
                                                                    // natural
                                                                    // order
        for (int x : ia)
            pq1.offer(x);
        for (int x : ia)
            // review queue
            System.out.print(pq1.poll() + " ");
        System.out.println("");
        PQsort pqs = new PQsort(); // get a Comparator
        PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs); // use
                                                                            // Comparator
        for (int x : ia)
            // load queue
            pq2.offer(x);
        System.out.println("size " + pq2.size());
        System.out.println("peek " + pq2.peek());
        System.out.println("size " + pq2.size());
        System.out.println("poll " + pq2.poll());
        System.out.println("size " + pq2.size());
        for (int x : ia)
            // review queue
            System.out.print(pq2.poll() + " ");
    }
}

Did you consider reading the Javadoc before you posted? Instead of posting? — user207421
– user207421, Commented May 23, 2012 at 10:18

NPE · Accepted Answer · 2012-05-23 07:37:27Z

1

Javadoc explains:

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

In other words, being able to specify the initial capacity is a way to optimize performance if one discovers that the queue spends too much time growing its internal array.

answered May 23, 2012 at 7:37

NPE

503k114 gold badges970 silver badges1k bronze badges

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

1 Comment

Jean Logeart Over a year ago

You may have the same question for ArrayList (and some other collections): stackoverflow.com/questions/3564837/capacity-of-arraylist

UVM · Accepted Answer · 2012-05-23 07:40:53Z

0

The API docs do explain what the capacity is. It's the size of the internal array.

http://download.java.net/jdk7/archive/b123/docs/api/java/util/PriorityQueue.html

Allowing you to specify an initial capacity is a small optimization. 
If you know how many entries you will need, you can save the (tiny) time 
spent growing the queue to the required size, by sizing it correctly 
from the start.

answered May 23, 2012 at 7:40

UVM

9,9247 gold badges43 silver badges66 bronze badges

Collectives™ on Stack Overflow

PriorityQueue clarification in Java

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related