tlx
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
RadixHeap< ValueType, KeyExtract, KeyType, Radix > Class Template Reference

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
 
RadixHeapoperator= (const RadixHeap &)=default
 
 RadixHeap (RadixHeap &&)=default
 
RadixHeapoperator= (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. More...
 
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. More...
 
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) More...
 
bucket_index_type push (const value_type &value)
 Insert element with priority key. More...
 
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) More...
 
bool empty () const
 Indicates whether size() == 0. More...
 
size_t size () const
 Returns number of elements currently stored. More...
 
key_type peak_top_key () const
 Returns currently smallest key without updating the insertion limit. More...
 
const value_typetop ()
 Returns currently smallest key and data. More...
 
void pop ()
 Removes smallest element. More...
 
void swap_top_bucket (bucket_data_type &exchange_bucket)
 Exchanges the top buckets with an empty user provided bucket. More...
 
void clear ()
 Clears all internal queues and resets insertion limit. More...
 

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
 

Detailed Description

template<typename ValueType, typename KeyExtract, typename KeyType, unsigned Radix = 8>
class tlx::RadixHeap< ValueType, KeyExtract, KeyType, Radix >

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

Template Parameters
KeyTypeHas to be an unsigned integer type
DataTypeType of data payload
RadixA power of two <= 64.

Definition at line 376 of file radix_heap.hpp.

Member Typedef Documentation

using bucket_data_type = std::vector<value_type>

Definition at line 402 of file radix_heap.hpp.

using bucket_index_type = size_t

Definition at line 386 of file radix_heap.hpp.

Definition at line 394 of file radix_heap.hpp.

Definition at line 391 of file radix_heap.hpp.

using key_type = KeyType

Definition at line 384 of file radix_heap.hpp.

using ranked_key_type = typename Encoder::rank_type
protected

Definition at line 392 of file radix_heap.hpp.

using value_type = ValueType

Definition at line 385 of file radix_heap.hpp.

Constructor & Destructor Documentation

RadixHeap ( KeyExtract  key_extract = KeyExtract { })
inlineexplicit

Definition at line 404 of file radix_heap.hpp.

RadixHeap ( const RadixHeap< ValueType, KeyExtract, KeyType, Radix > &  )
default
RadixHeap ( RadixHeap< ValueType, KeyExtract, KeyType, Radix > &&  )
default

Member Function Documentation

void clear ( )
inline

Clears all internal queues and resets insertion limit.

Definition at line 545 of file radix_heap.hpp.

bucket_index_type emplace ( const key_type  key,
Args &&...  args 
)
inline

Construct and insert element with priority key.

Warning
In contrast to all other methods the key has to be provided explicitly as the first argument. All other arguments are passed to the constructor of the element.

Definition at line 433 of file radix_heap.hpp.

void emplace_in_bucket ( const bucket_index_type  idx,
Args &&...  args 
)
inline

Construct and insert element into bucket idx (useful if an item was inserted into the same bucket directly before)

Warning
Calling any method which updates the current can invalidate this hint

Definition at line 454 of file radix_heap.hpp.

bucket_index_type emplace_keyfirst ( const key_type  key,
Args &&...  args 
)
inline

In case the first parameter can be directly casted into key_type, using this method avoid repeating it.

Definition at line 445 of file radix_heap.hpp.

bool empty ( ) const
inline

Indicates whether size() == 0.

Definition at line 497 of file radix_heap.hpp.

bucket_index_type get_bucket ( const value_type value) const
inline

Definition at line 417 of file radix_heap.hpp.

bucket_index_type get_bucket_key ( const key_type  key) const
inline

Definition at line 421 of file radix_heap.hpp.

void initialize_ ( )
inlineprotected

Definition at line 563 of file radix_heap.hpp.

RadixHeap& operator= ( const RadixHeap< ValueType, KeyExtract, KeyType, Radix > &  )
default
RadixHeap& operator= ( RadixHeap< ValueType, KeyExtract, KeyType, Radix > &&  )
default
key_type peak_top_key ( ) const
inline

Returns currently smallest key without updating the insertion limit.

Definition at line 507 of file radix_heap.hpp.

void pop ( )
inline

Removes smallest element.

Warning
Updates insertion limit; no smaller keys can be inserted later

Definition at line 522 of file radix_heap.hpp.

bucket_index_type push ( const value_type value)
inline

Insert element with priority key.

Definition at line 467 of file radix_heap.hpp.

void push_to_bucket ( const bucket_index_type  idx,
const value_type value 
)
inline

Insert element into specific bucket (useful if an item was inserted into the same bucket directly before)

Warning
Calling any method which updates the current can invalidate this hint

Definition at line 482 of file radix_heap.hpp.

void reorganize_ ( )
inlineprotected

Definition at line 574 of file radix_heap.hpp.

size_t size ( ) const
inline

Returns number of elements currently stored.

Definition at line 502 of file radix_heap.hpp.

void swap_top_bucket ( bucket_data_type exchange_bucket)
inline

Exchanges the top buckets with an empty user provided bucket.

Can be used for bulk removals and may reduce allocation overhead

Warning
The exchange bucket has to be empty
Updates insertion limit; no smaller keys can be inserted later

Definition at line 534 of file radix_heap.hpp.

const value_type& top ( )
inline

Returns currently smallest key and data.

Warning
Updates insertion limit; no smaller keys can be inserted later

Definition at line 515 of file radix_heap.hpp.

Member Data Documentation

bucket_map_type bucket_map_
protected

Definition at line 556 of file radix_heap.hpp.

std::array<bucket_data_type, num_buckets> buckets_data_
protected

Definition at line 558 of file radix_heap.hpp.

size_t current_bucket_
protected

Definition at line 554 of file radix_heap.hpp.

constexpr bool debug
staticprivate

Definition at line 381 of file radix_heap.hpp.

Definition at line 561 of file radix_heap.hpp.

ranked_key_type insertion_limit_
protected

Definition at line 553 of file radix_heap.hpp.

KeyExtract key_extract_
protected

Definition at line 551 of file radix_heap.hpp.

std::array<ranked_key_type, num_buckets> mins_
protected

Definition at line 560 of file radix_heap.hpp.

constexpr unsigned num_buckets
staticprotected

Definition at line 399 of file radix_heap.hpp.

constexpr unsigned num_layers
staticprotected

Definition at line 397 of file radix_heap.hpp.

constexpr unsigned radix
static

Definition at line 388 of file radix_heap.hpp.

constexpr unsigned radix_bits
staticprotected

Definition at line 396 of file radix_heap.hpp.

size_t size_
protected

Definition at line 552 of file radix_heap.hpp.


The documentation for this class was generated from the following file: