tlx
|
This class implements a monotonic integer min priority queue, more specific a multi-level radix heap. More...
#include <radix_heap.hpp>
Public Types | |
using | key_type = KeyType |
using | value_type = ValueType |
using | bucket_index_type = size_t |
using | bucket_data_type = std::vector< value_type > |
Public Member Functions | |
RadixHeap (KeyExtract key_extract=KeyExtract { }) | |
RadixHeap (const RadixHeap &)=default | |
RadixHeap & | operator= (const RadixHeap &)=default |
RadixHeap (RadixHeap &&)=default | |
RadixHeap & | operator= (RadixHeap &&)=default |
bucket_index_type | get_bucket (const value_type &value) const |
bucket_index_type | get_bucket_key (const key_type key) const |
template<typename... Args> | |
bucket_index_type | emplace (const key_type key, Args &&... args) |
Construct and insert element with priority key. | |
template<typename... Args> | |
bucket_index_type | emplace_keyfirst (const key_type key, Args &&... args) |
In case the first parameter can be directly casted into key_type, using this method avoid repeating it. | |
template<typename... Args> | |
void | emplace_in_bucket (const bucket_index_type idx, Args &&... args) |
Construct and insert element into bucket idx (useful if an item was inserted into the same bucket directly before) | |
bucket_index_type | push (const value_type &value) |
Insert element with priority key. | |
void | push_to_bucket (const bucket_index_type idx, const value_type &value) |
Insert element into specific bucket (useful if an item was inserted into the same bucket directly before) | |
bool | empty () const |
Indicates whether size() == 0. | |
size_t | size () const |
Returns number of elements currently stored. | |
key_type | peak_top_key () const |
Returns currently smallest key without updating the insertion limit. | |
const value_type & | top () |
Returns currently smallest key and data. | |
void | pop () |
Removes smallest element. | |
void | swap_top_bucket (bucket_data_type &exchange_bucket) |
Exchanges the top buckets with an empty user provided bucket. | |
void | clear () |
Clears all internal queues and resets insertion limit. | |
Static Public Attributes | |
static constexpr unsigned | radix |
Protected Types | |
using | Encoder = radix_heap_detail::IntegerRank< key_type > |
using | ranked_key_type = typename Encoder::rank_type |
using | bucket_map_type = radix_heap_detail::BucketComputation< Radix, ranked_key_type > |
Protected Member Functions | |
void | initialize_ () |
void | reorganize_ () |
Protected Attributes | |
KeyExtract | key_extract_ |
size_t | size_ |
ranked_key_type | insertion_limit_ |
size_t | current_bucket_ |
bucket_map_type | bucket_map_ |
std::array< bucket_data_type, num_buckets > | buckets_data_ |
std::array< ranked_key_type, num_buckets > | mins_ |
radix_heap_detail::BitArray< num_buckets > | filled_ |
Static Protected Attributes | |
static constexpr unsigned | radix_bits |
static constexpr unsigned | num_layers |
static constexpr unsigned | num_buckets |
Static Private Attributes | |
static constexpr bool | debug |
This class implements a monotonic integer min priority queue, more specific a multi-level radix heap.
Here, monotonic refers to the fact that the heap maintains an insertion limit and does not allow the insertion of keys smaller than this limit. The frontier is increased to the current minimum when invoking the methods top(), pop() and swap_top_bucket(). To query the currently smallest item without updating the insertion limit use peak_top_key().
We implement a two level radix heap. Let k=sizeof(KeyType)*8 be the number of bits in a key. In contrast to an ordinary radix heap which contains k buckets, we maintain ceil(k/log2(Radix)) rows each containing Radix-many buckets. This reduces the number of move operations when reorganizing the data structure.
The implementation loosly follows the description of "An Experimental Study of Priority Queues in External Memory" [Bregel et al.] and is also inspired by https://github.com/iwiwi/radix-heap
KeyType | Has to be an unsigned integer type |
DataType | Type of data payload |
Radix | A power of two <= 64. |
Definition at line 378 of file radix_heap.hpp.
using bucket_data_type = std::vector<value_type> |
Definition at line 404 of file radix_heap.hpp.
using bucket_index_type = size_t |
Definition at line 388 of file radix_heap.hpp.
|
protected |
Definition at line 395 of file radix_heap.hpp.
|
protected |
Definition at line 393 of file radix_heap.hpp.
using key_type = KeyType |
Definition at line 386 of file radix_heap.hpp.
|
protected |
Definition at line 394 of file radix_heap.hpp.
using value_type = ValueType |
Definition at line 387 of file radix_heap.hpp.
|
inlineexplicit |
Definition at line 406 of file radix_heap.hpp.
|
default |
|
default |
|
inline |
Clears all internal queues and resets insertion limit.
Definition at line 547 of file radix_heap.hpp.
|
inline |
Construct and insert element with priority key.
Definition at line 435 of file radix_heap.hpp.
|
inline |
Construct and insert element into bucket idx (useful if an item was inserted into the same bucket directly before)
Definition at line 456 of file radix_heap.hpp.
|
inline |
In case the first parameter can be directly casted into key_type, using this method avoid repeating it.
Definition at line 447 of file radix_heap.hpp.
|
inline |
Indicates whether size() == 0.
Definition at line 499 of file radix_heap.hpp.
|
inline |
Definition at line 419 of file radix_heap.hpp.
|
inline |
Definition at line 423 of file radix_heap.hpp.
|
inlineprotected |
Definition at line 565 of file radix_heap.hpp.
|
default |
|
default |
|
inline |
Returns currently smallest key without updating the insertion limit.
Definition at line 509 of file radix_heap.hpp.
|
inline |
Removes smallest element.
Definition at line 524 of file radix_heap.hpp.
|
inline |
Insert element with priority key.
Definition at line 469 of file radix_heap.hpp.
|
inline |
Insert element into specific bucket (useful if an item was inserted into the same bucket directly before)
Definition at line 484 of file radix_heap.hpp.
|
inlineprotected |
Definition at line 576 of file radix_heap.hpp.
|
inline |
Returns number of elements currently stored.
Definition at line 504 of file radix_heap.hpp.
|
inline |
Exchanges the top buckets with an empty user provided bucket.
Can be used for bulk removals and may reduce allocation overhead
Definition at line 536 of file radix_heap.hpp.
|
inline |
Returns currently smallest key and data.
Definition at line 517 of file radix_heap.hpp.
|
protected |
Definition at line 558 of file radix_heap.hpp.
|
protected |
Definition at line 560 of file radix_heap.hpp.
|
protected |
Definition at line 556 of file radix_heap.hpp.
|
staticconstexprprivate |
Definition at line 383 of file radix_heap.hpp.
|
protected |
Definition at line 563 of file radix_heap.hpp.
|
protected |
Definition at line 555 of file radix_heap.hpp.
|
protected |
Definition at line 553 of file radix_heap.hpp.
|
protected |
Definition at line 562 of file radix_heap.hpp.
|
staticconstexprprotected |
Definition at line 401 of file radix_heap.hpp.
|
staticconstexprprotected |
Definition at line 399 of file radix_heap.hpp.
|
staticconstexpr |
Definition at line 390 of file radix_heap.hpp.
|
staticconstexprprotected |
Definition at line 398 of file radix_heap.hpp.
|
protected |
Definition at line 554 of file radix_heap.hpp.