Initial Capacity of Priority Queue in Java

Question

I'm confused by the usage of the initial capacity of Priority Queue in Java. As is shown in official documentation, there is a constructor with initial capacity as a parameter. But when I specify the initial capacity with that constructor and start putting integers into it, the size of the priority queue gets larger than the initial capacity.

For example, I specify the initial capacity of a PQ to 3 and put 10 different numbers into it so that I can get the 3rd smallest number, but it turns out that there are 10 numbers in that queue. To deal with this, I always have to remove some numbers manually, so I wonder how the initial capacity works or in which case should I use the initial capacity.

Thank you!

Answer 1

The priority queue is backed by some data structure - specifically, an array. The initial capacity is how big this array is initially.

This is described in the documentation:

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 point of being able to specify the capacity is not to limit the number of elements, but rather to give a hint as to how big the array needs to be, in order to avoid having to grow that array (which takes time, memory etc).

So, yes, if you're going to use a priority queue, you need to remove the unwanted elements yourself (or just discard the queue once you've got the number of elements you want out of it).