Fast Priority Queues for Cached Memory

has to be taken into account in order to design algorithms which
perform well in practice. We advocates the approach to adapt external
memory algorithms to this purpose. We exemplify this approach and the
practical issues involved by engineering a fast priority queue suited
to external memory and cached memory which is based on k-way merging.
It improves previous external memory algorithms by constant factors
crucial for transferring it to cached memory. Running in the cache
hierarchy of a workstation the algorithm is around three times faster
than an optimized binary heap implementation.