Thrill  0.1
RadixHeap< ValueType, KeyExtract, KeyType, Radix > Class Template Reference

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.

+ Collaboration diagram for RadixHeap< ValueType, KeyExtract, KeyType, Radix >:

#include <radix_heap.hpp>

Public Types

using bucket_data_type = std::vector< value_type >
 
using bucket_index_type = size_t
 
using key_type = KeyType
 
using value_type = ValueType
 

Public Member Functions

 RadixHeap (KeyExtract key_extract=KeyExtract { })
 
 RadixHeap (const RadixHeap &)=default
 
 RadixHeap (RadixHeap &&)=default
 
void clear ()
 Clears all internal queues and resets insertion limit. More...
 
template<typename... Args>
bucket_index_type emplace (const key_type key, Args &&... args)
 
template<typename... Args>
void emplace_in_bucket (const bucket_index_type idx, Args &&... args)
 
template<typename... Args>
bucket_index_type emplace_keyfirst (const key_type key, Args &&... args)
 
bool empty () const
 Indicates whether size() == 0. More...
 
bucket_index_type get_bucket (const value_type &value) const
 
bucket_index_type get_bucket_key (const key_type key) const
 
RadixHeapoperator= (const RadixHeap &)=default
 
RadixHeapoperator= (RadixHeap &&)=default
 
key_type peak_top_key () const
 Returns currently smallest key without updating the insertion limit. More...
 
void pop ()
 
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)
 
size_t size () const
 Returns number of elements currently stored. More...
 
void swap_top_bucket (bucket_data_type &exchange_bucket)
 
const value_typetop ()
 

Static Public Attributes

static constexpr unsigned radix = Radix
 

Protected Types

using bucket_map_type = radix_heap_detail::BucketComputation< Radix, ranked_key_type >
 
using Encoder = radix_heap_detail::IntegerRank< key_type >
 
using ranked_key_type = typename Encoder::rank_type
 

Protected Member Functions

void initialize_ ()
 
void reorganize_ ()
 

Protected Attributes

bucket_map_type bucket_map_
 
std::array< bucket_data_type, num_bucketsbuckets_data_
 
size_t current_bucket_ { 0 }
 
radix_heap_detail::BitArray< num_bucketsfilled_
 
ranked_key_type insertion_limit_ { 0 }
 
KeyExtract key_extract_
 
std::array< ranked_key_type, num_bucketsmins_
 
size_t size_ { 0 }
 

Static Protected Attributes

static constexpr unsigned num_buckets = bucket_map_type::num_buckets
 
static constexpr unsigned num_layers
 
static constexpr unsigned radix_bits = tlx::Log2<radix>::floor
 

Static Private Attributes

static constexpr bool debug = false
 

Member Typedef Documentation

◆ bucket_data_type

using bucket_data_type = std::vector<value_type>

Definition at line 402 of file radix_heap.hpp.

◆ bucket_index_type

using bucket_index_type = size_t

Definition at line 386 of file radix_heap.hpp.

◆ bucket_map_type

Definition at line 394 of file radix_heap.hpp.

◆ Encoder

Definition at line 391 of file radix_heap.hpp.

◆ key_type

using key_type = KeyType

Definition at line 384 of file radix_heap.hpp.

◆ ranked_key_type

using ranked_key_type = typename Encoder::rank_type
protected

Definition at line 392 of file radix_heap.hpp.

◆ value_type

using value_type = ValueType

Definition at line 385 of file radix_heap.hpp.

Constructor & Destructor Documentation

◆ RadixHeap() [1/3]

RadixHeap ( KeyExtract  key_extract = KeyExtract { })
inlineexplicit

Definition at line 404 of file radix_heap.hpp.

◆ RadixHeap() [2/3]

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

◆ RadixHeap() [3/3]

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

Member Function Documentation

◆ clear()

void clear ( )
inline

Clears all internal queues and resets insertion limit.

Definition at line 545 of file radix_heap.hpp.

References gen_data::x.

◆ emplace()

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.

◆ emplace_in_bucket()

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.

◆ emplace_keyfirst()

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.

◆ empty()

bool empty ( ) const
inline

Indicates whether size() == 0.

Definition at line 497 of file radix_heap.hpp.

◆ get_bucket()

bucket_index_type get_bucket ( const value_type value) const
inline

Definition at line 417 of file radix_heap.hpp.

◆ get_bucket_key()

bucket_index_type get_bucket_key ( const key_type  key) const
inline

Definition at line 421 of file radix_heap.hpp.

◆ initialize_()

void initialize_ ( )
inlineprotected

Definition at line 563 of file radix_heap.hpp.

References BitArray< Size >::clear_all(), max(), and min().

◆ operator=() [1/2]

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

◆ operator=() [2/2]

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

◆ peak_top_key()

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.

◆ pop()

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.

◆ push()

bucket_index_type push ( const value_type value)
inline

Insert element with priority key.

Definition at line 467 of file radix_heap.hpp.

◆ push_to_bucket()

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.

◆ reorganize_()

void reorganize_ ( )
inlineprotected

◆ size()

size_t size ( ) const
inline

Returns number of elements currently stored.

Definition at line 502 of file radix_heap.hpp.

◆ swap_top_bucket()

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.

◆ top()

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_

bucket_map_type bucket_map_
protected

Definition at line 556 of file radix_heap.hpp.

◆ buckets_data_

std::array<bucket_data_type, num_buckets> buckets_data_
protected

Definition at line 558 of file radix_heap.hpp.

◆ current_bucket_

size_t current_bucket_ { 0 }
protected

Definition at line 554 of file radix_heap.hpp.

◆ debug

constexpr bool debug = false
staticprivate

Definition at line 381 of file radix_heap.hpp.

◆ filled_

Definition at line 561 of file radix_heap.hpp.

◆ insertion_limit_

ranked_key_type insertion_limit_ { 0 }
protected

Definition at line 553 of file radix_heap.hpp.

◆ key_extract_

KeyExtract key_extract_
protected

Definition at line 551 of file radix_heap.hpp.

◆ mins_

std::array<ranked_key_type, num_buckets> mins_
protected

Definition at line 560 of file radix_heap.hpp.

◆ num_buckets

constexpr unsigned num_buckets = bucket_map_type::num_buckets
staticprotected

Definition at line 399 of file radix_heap.hpp.

◆ num_layers

constexpr unsigned num_layers
staticprotected
Initial value:

Definition at line 397 of file radix_heap.hpp.

◆ radix

constexpr unsigned radix = Radix
static

Definition at line 388 of file radix_heap.hpp.

◆ radix_bits

constexpr unsigned radix_bits = tlx::Log2<radix>::floor
staticprotected

Definition at line 396 of file radix_heap.hpp.

◆ size_

size_t size_ { 0 }
protected

Definition at line 552 of file radix_heap.hpp.


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