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
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. 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_type &	top ()
	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

KeyType	Has to be an unsigned integer type
DataType	Type of data payload
Radix	A power of two <= 64.

Definition at line 377 of file radix_heap.hpp.

Member Typedef Documentation

using bucket_data_type = std::vector<value_type>

Definition at line 403 of file radix_heap.hpp.

using bucket_index_type = size_t

Definition at line 387 of file radix_heap.hpp.

using bucket_map_type = radix_heap_detail::BucketComputation<Radix, ranked_key_type>

protected

Definition at line 395 of file radix_heap.hpp.

using Encoder = radix_heap_detail::IntegerRank<key_type>

protected

Definition at line 392 of file radix_heap.hpp.

using key_type = KeyType

Definition at line 385 of file radix_heap.hpp.

using ranked_key_type = typename Encoder::rank_type

protected

Definition at line 393 of file radix_heap.hpp.

using value_type = ValueType

Definition at line 386 of file radix_heap.hpp.

Constructor & Destructor Documentation

RadixHeap ( KeyExtract  key_extract = KeyExtract { } )

inlineexplicit

Definition at line 405 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 546 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 434 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 455 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 446 of file radix_heap.hpp.

bool empty ( ) const

inline

Indicates whether size() == 0.

Definition at line 498 of file radix_heap.hpp.

bucket_index_type get_bucket ( const value_type &  value ) const

inline

Definition at line 418 of file radix_heap.hpp.

bucket_index_type get_bucket_key ( const key_type  key ) const

inline

Definition at line 422 of file radix_heap.hpp.

void initialize_ ( )

inlineprotected

Definition at line 564 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 508 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 523 of file radix_heap.hpp.

bucket_index_type push ( const value_type &  value )

inline

Insert element with priority key.

Definition at line 468 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 483 of file radix_heap.hpp.

void reorganize_ ( )

inlineprotected

Definition at line 575 of file radix_heap.hpp.

size_t size ( ) const

inline

Returns number of elements currently stored.

Definition at line 503 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 535 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 516 of file radix_heap.hpp.

Member Data Documentation

bucket_map_type bucket_map_

protected

Definition at line 557 of file radix_heap.hpp.

std::array<bucket_data_type, num_buckets> buckets_data_

protected

Definition at line 559 of file radix_heap.hpp.

size_t current_bucket_

protected

Definition at line 555 of file radix_heap.hpp.

constexpr bool debug

staticprivate

Definition at line 382 of file radix_heap.hpp.

radix_heap_detail::BitArray<num_buckets> filled_

protected

Definition at line 562 of file radix_heap.hpp.

ranked_key_type insertion_limit_

protected

Definition at line 554 of file radix_heap.hpp.

KeyExtract key_extract_

protected

Definition at line 552 of file radix_heap.hpp.

std::array<ranked_key_type, num_buckets> mins_

protected

Definition at line 561 of file radix_heap.hpp.

constexpr unsigned num_buckets

staticprotected

Definition at line 400 of file radix_heap.hpp.

constexpr unsigned num_layers

staticprotected

Definition at line 398 of file radix_heap.hpp.

constexpr unsigned radix

static

Definition at line 389 of file radix_heap.hpp.

constexpr unsigned radix_bits

staticprotected

Definition at line 397 of file radix_heap.hpp.

size_t size_

protected

Definition at line 553 of file radix_heap.hpp.

---

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

• tlx/container/radix_heap.hpp