External memory priority queue implementation. More...
#include <tpie/priority_queue.h>
Public Member Functions | |
priority_queue (double f=1.0, float b=0.0625) | |
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... | |
External memory priority queue implementation.
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 77 of file priority_queue.h.
tpie::priority_queue< T, Comparator, OPQType >::priority_queue | ( | double | f = 1.0 , |
float | b = 0.0625 |
||
) |
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 358 of file priority_queue.h.
void tpie::priority_queue< T, Comparator, OPQType >::pop | ( | ) |
Remove the top element from the priority queue.
Definition at line 299 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 363 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 217 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 325 of file priority_queue.h.