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.
1
-
I'm confused. In the beggining, javadocs say that it is implemented uding a heap, but later it says: "A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue." Which one is it? and if it's a heap, what is the array for?Martin Klosi– Martin Klosi2014-10-31 21:46:51 +00:00Commented Oct 31, 2014 at 21:46
Add a comment
|
2 Answers
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
Comments
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.
