Editing Priority queue (section)

=== ''K''-element operations ===
In this setting, operations on a priority queue is generalized to a batch of <math display="inline">k</math> elements.
For instance, ''k_extract-min'' deletes the <math display="inline">k</math> smallest elements of the priority queue and returns those. 

In a [[Parallel programming model|shared-memory setting]], the parallel priority queue can be easily implemented using parallel [[binary search trees]] and [[join-based tree algorithms]].  In particular, ''k_extract-min'' corresponds to a ''split'' on the binary search tree that has <math display="inline">O(\log n)</math> cost and yields a tree that contains the <math display="inline">k</math> smallest elements.  ''k_insert'' can be applied by a ''union'' of the original priority queue and the batch of insertions.  If the batch is already sorted by the key, ''k_insert'' has <math display="inline">O(k\log (1+\frac{n}{k}))</math> cost.  Otherwise, we need to first sort the batch, so the cost will be <math display="inline">O(k\log (1+\frac{n}{k})+k\log k)=O(k\log n)</math>.  Other operations for priority queue can be applied similarly.  For instance, ''k_decrease-key'' can be done by first applying ''difference'' and then ''union'', which first deletes the elements and then inserts them back with the updated keys.  All these operations are highly parallel, and the theoretical and practical efficiency can be found in related research papers.<ref name="join-based">{{citation
 | last1 = Blelloch | first1 = Guy E.
 | last2 = Ferizovic | first2 = Daniel
 | last3 = Sun | first3 = Yihan
 | contribution = Just Join for Parallel Ordered Sets
 | doi = 10.1145/2935764.2935768
 | isbn = 978-1-4503-4210-0
 | pages = 253–264
 | publisher = ACM
 | title = Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)
 | year = 2016 | arxiv = 1602.02120
 | s2cid = 2897793
 }}</ref><ref name="pam">{{citation
 | last1 = Blelloch | first1 = Guy E.
 | last2 = Ferizovic | first2 = Daniel
 | last3 = Sun | first3 = Yihan
 | contribution = PAM: parallel augmented maps
 | pages = 290–304
 | title = Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
 | publisher = ACM
 | year = 2018}}</ref>

The rest of this section discusses a queue-based algorithm on distributed memory. We assume each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors.

[[File:BulkDeletionPQ.svg|thumb|''k_extract-min'' is executed on a priority queue with three processors. The green elements are returned and removed from the priority queue.]]

A ''k_insert'' operation assigns the elements uniformly random to the processors which insert the elements into their local queues. Note that single elements can still be inserted into the queue. Using this strategy the global smallest elements are in the union of the local smallest elements of every processor with high probability. Thus each processor holds a representative part of the global priority queue.

This property is used when ''k_extract-min'' is executed, as the smallest <math display="inline">m</math> elements of each local queue are removed and collected in a result set. The elements in the result set are still associated with their original processor. The number of elements <math display="inline">m</math> that is removed from each local queue depends on <math display="inline">k</math> and the number of processors <math display="inline">p</math>. 
<ref name=AlgToolbox>{{cite book | first1=Peter | last1=Sanders | first2=Kurt | last2=Mehlhorn | first3=Martin | last3=Dietzfelbinger | first4=Roman | last4= Dementiev | title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox | publisher=Springer International Publishing | date=2019 | pages=226–229 | doi=10.1007/978-3-030-25209-0| isbn=978-3-030-25208-3 | s2cid=201692657 }}</ref>
By parallel selection the <math display="inline">k</math> smallest elements of the result set are determined. With high probability these are the global <math display="inline">k</math> smallest elements. If not, <math display="inline">m</math> elements are again removed from each local queue and put into the result set. This is done until the global <math display="inline">k</math> smallest elements are in the result set. Now these <math display="inline">k</math> elements can be returned. All other elements of the result set are inserted back into their local queues. The running time of ''k_extract-min'' is expected <math display="inline"> O(\frac{k}{p} \log(n)) </math>, where <math display="inline">k = \Omega(p \cdot \log (p))</math> and <math display="inline">n</math> is the size of the priority queue.<ref name="AlgToolbox"/>

The priority queue can be further improved by not moving the remaining elements of the result set directly back into the local queues after a ''k_extract-min'' operation. This saves moving elements back and forth all the time between the result set and the local queues.

By removing several elements at once a considerable speedup can be reached. But not all algorithms can use this kind of priority queue. Dijkstra's algorithm for example can not work on several nodes at once. The algorithm takes the node with the smallest distance from the priority queue and calculates new distances for all its neighbor nodes. If you would take out <math display="inline">k</math> nodes, working at one node could change the distance of another one of the <math display="inline">k</math> nodes. So using k-element operations destroys the label setting property of Dijkstra's algorithm.