CODEWITHSUNDEEP
javaheappriority-queue
gran33
gran33

Reputation: 12951

JAVA- PriorityQueue implementation

Java, in the implementation of the PriorityQueue object, uses Heap. Does the Implementation (by Java) parallel the "heapify" operation after the poll() operation (by another thread, for example)?

Thanks in advance.

Upvotes: 2

Views: 1389

Answers (2)

Miquel
Miquel

Reputation: 15675

No, it doesn't paralelize it. The algorithm is just not designed that way.

Additionally, consider that, since you have to wait for the whole operation to finish, you'd only get an advantage out of multi-threading it if there were significant code blocks where the computer just has to wait (e.g. retrieving a web page). Since this is clearly not the case for a heap, there's no benefit from it.

One more thing: whenever multi-threading is included, there's also a price to pay: maintenance becomes more complicated, there's CPU time spent in thread instantiation and lock management, etc...

In this case, it wouldn't help. A different issue would be if you wanted to have a data structure that needs to work distributedly across several computers in which case, a distributed variant would have to be developed, but only if the paralelization benefits outweight the overhead involved in distributing the data.

Upvotes: 1

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70931

The heapify operation only considers one element at a time, sinking or sifting it up. I don't know of a way in which it can be parallelized.

Still if you want to make sure why don't you have a look at the code?

EDIT: I am now sure at least for openjdk's implementation

Upvotes: 3

Related Questions