External memory priority queue implementation. More...
#include <tpie/priority_queue.h>
Public Member Functions | |
| priority_queue (double f=1.0, float b=default_blocksize, stream_size_type n=std::numeric_limits< stream_size_type >::max()) | |
| Constructor. More... | |
| ~priority_queue () | |
| Destructor. More... | |
| void | push (const T &x) |
| Insert an element into the priority queue. More... | |
| void | pop () |
| Remove the top element from the priority queue. More... | |
| const T & | top () |
| See what's on the top of the priority queue. More... | |
| stream_size_type | size () const |
| Returns the size of the queue. More... | |
| bool | empty () const |
| Return true if queue is empty otherwise false. More... | |
| template<typename F > | |
| F | pop_equals (F f) |
| Pop all elements with priority equal to that of the top element, and process each by invoking f's call operator on the element. More... | |
Static Public Member Functions | |
| static memory_size_type | memory_usage (stream_size_type n, float b=default_blocksize) |
| Compute the maximal amount of memory it makes sence to give a queue that will contain atmount n elements. More... | |
Static Public Attributes | |
| static constexpr float | default_blocksize = 0.0625 |
External memory priority queue implementation.
The top of the queue is the least element in the specified ordering.
Originally implemented by Lars Hvam Petersen for his Master's thesis titled "External Priority Queues in Practice", June 2007. This implementation, named "PQSequence3", is the fastest among the priority queue implementations studied in the paper. Inspiration: Sanders - Fast priority queues for cached memory (1999).
For an overview of the algorithm, refer to Sanders (1999) section 2 and figure 1, or Lars Hvam's thesis, section 4.4.
In the debug log, the priority queue reports two values setting_k and setting_m. The priority queue has a maximum capacity which is on the order of setting_m * setting_k**setting_k elements (where ** denotes exponentiation).
However, even with as little as 8 MB of memory, this maximum capacity in practice exceeds 2**48, corresponding to a petabyte-sized dataset of 32-bit integers.
Definition at line 78 of file priority_queue.h.
| tpie::priority_queue< T, Comparator, OPQType >::priority_queue | ( | double | f = 1.0, |
| float | b = default_blocksize, |
||
| stream_size_type | n = std::numeric_limits<stream_size_type>::max() |
||
| ) |
Constructor.
| f | Factor of memory that the priority queue is allowed to use. |
| b | Block factor |
Definition at line 22 of file priority_queue.h.
| tpie::priority_queue< T, Comparator, OPQType >::~priority_queue | ( | ) |
| bool tpie::priority_queue< T, Comparator, OPQType >::empty | ( | ) | const |
Return true if queue is empty otherwise false.
Definition at line 382 of file priority_queue.h.
|
static |
Compute the maximal amount of memory it makes sence to give a queue that will contain atmount n elements.
Definition at line 49 of file priority_queue.h.
| void tpie::priority_queue< T, Comparator, OPQType >::pop | ( | ) |
Remove the top element from the priority queue.
Definition at line 323 of file priority_queue.h.
| F tpie::priority_queue< T, Comparator, OPQType >::pop_equals | ( | F | f | ) |
Pop all elements with priority equal to that of the top element, and process each by invoking f's call operator on the element.
| f | - assumed to have a call operator with parameter of type T. |
Definition at line 387 of file priority_queue.h.
| void tpie::priority_queue< T, Comparator, OPQType >::push | ( | const T & | x | ) |
Insert an element into the priority queue.
| x | The item |
Definition at line 241 of file priority_queue.h.
| stream_size_type tpie::priority_queue< T, Comparator, OPQType >::size | ( | ) | const |
| const T & tpie::priority_queue< T, Comparator, OPQType >::top | ( | ) |
See what's on the top of the priority queue.
Definition at line 349 of file priority_queue.h.