My Project
Priority Queue
Author
Roman Dementiev (2006)

A priority queue is a data structure that provides a restricted subset of container functionality: it provides insertion of elements, and inspection and removal of the top element. It is guaranteed that the top element is the largest element in the priority queue, where the function object Cmp is used for comparisons. Priority queues do not allow iteration through its elements.

External memory priority queues are the central data structures for many I/O efficient graph algorithms ([ZehPhd] [ChiEtAl95] [MSS03]). The main technique in these algorithms is time-forward processing ([ChiEtAl95] [Arg95]), easily realizable by an I/O efficient priority queue. I/O efficient priority queues also find application in large-scale discrete event simulation and online sorting. The STXXL implementation of priority queues is based on [San00b]. An operation of this priority queue, called sequence heap, takes $ \mathcal{O}(\frac{1}{B}\log_{M/B}(I/B)) $ amortized I/Os, where $ I $ is the total number of insertions into the priority queue. This queue needs less than a third of I/Os used by other similar cache (I/O) efficient priority queues (e.g. [Brengel00] [FJKT97]). The amortized run time of the STXXL priority queue are

operation internal work I/O (amortized)
insertion $ \mathcal{O}(\log I) $ $ \mathcal{O}(1/B) $
deletion $ \mathcal{O}(\log I) $ $ \mathcal{O}(1/B) $

where $ I $ is the number of performed operations.

A sequence heap maintains R merge groups $ G_1,\ldots, G_R $ where $ G_i $ holds up to k sorted sequences of size up to $ m k^{i-1} $, $ m << M $, see following figure. When group $ G_i $ overflows, all its sequences are merged, and the resulting sequence is put into group $ G_{i+1} $. Each group is equipped with a group buffer of size m to allow batched deletion from the sequences. The smallest elements of these buffers are deleted in small batches and stored in the deletion buffer. The elements are first inserted into the insertion priority queue. On deletion, one checks the minimum elements stored in the insertion priority queue and the deletion buffer.

The difference of our implementation to [San00b] is that a number of larger merge groups are explicitly kept in external memory. The sorted sequences in those groups only hold their first blocks in the main memory. The implementation supports parallel disks and overlaps I/O and computation. As in [San00b], the internal merging is based on loser trees [Knu98]. However, our implementation does not use sentinel elements.

san00b_pqueue_small.png
The structure of STXXL priority queue

stxxl::PRIORITY_QUEUE_GENERATOR

Since the stxxl::priority_queue has many setup parameters (internal memory buffer sizes, arity of mergers, number of internal and external memory merger groups, etc.) which are difficult to guess, STXXL provides a helper meta template program that searches for the optimum settings for user demands. This is necessary to limit the amount of main memory occupied by the different buffers of the data structure. The program is called stxxl::PRIORITY_QUEUE_GENERATOR.

The stxxl::PRIORITY_QUEUE_GENERATOR has the following template parameters:

Notes

Internal Memory Consumption of stxxl::priority_queue

Internal memory consumption of stxxl::priority_queue is bounded by the IntMemory template parameter in most situations.