are determined. With high probability these are the global smallest elements. If not, elements are again removed from each local queue and put into the result set. This is done until the global smallest elements are in the result set. Now these 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 , where and is the size of the priority queue. 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 nodes, working at one node could change the distance of another one of the nodes. So using k-element operations destroys the label setting property of Dijkstra's algorithm. See also Batch queue Command queue Job scheduler References Further reading External links C++ reference for std::priority_queue Descriptions by Lee Killough PQlib - Open source Priority Queue library for C libpqueue is a generic priority queue (heap) implementation (in C) used by the Apache HTTP Server project. Survey of known priority queue structures by Stefan Xenos UC Berkeley - Computer Science 61B - Lecture 24: Priority Queues (video) - introduction to priority queues using binary heap Abstract data types