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 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

RadixHeap &	operator= (const RadixHeap &)=default

RadixHeap &	operator= (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_type &	top ()

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_buckets >	buckets_data_

size_t	current_bucket_ { 0 }

radix_heap_detail::BitArray< num_buckets >	filled_

ranked_key_type	insertion_limit_ { 0 }

KeyExtract	key_extract_

std::array< ranked_key_type, num_buckets >	mins_

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

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

protected

Definition at line 394 of file radix_heap.hpp.

◆ Encoder

using Encoder = radix_heap_detail::IntegerRank<key_type>

protected

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

Definition at line 574 of file radix_heap.hpp.

References BitArray< Size >::clear_bit(), BitArray< Size >::find_lsb(), max(), BitArray< Size >::set_bit(), TLX_LIKELY, and gen_data::x.

◆ 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_

radix_heap_detail::BitArray<num_buckets> filled_

protected

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:

=

div_ceil(8 * sizeof(ranked_key_type), radix_bits)

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:

extlib/tlx/tlx/container/radix_heap.hpp

Detailed Description

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

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Static Private Attributes

Member Typedef Documentation

◆ bucket_data_type

◆ bucket_index_type

◆ bucket_map_type

◆ Encoder

◆ key_type

◆ ranked_key_type

◆ value_type

Constructor & Destructor Documentation

◆ RadixHeap() [1/3]

◆ RadixHeap() [2/3]

◆ RadixHeap() [3/3]

Member Function Documentation

◆ clear()

◆ emplace()

◆ emplace_in_bucket()

◆ emplace_keyfirst()

◆ empty()

◆ get_bucket()

◆ get_bucket_key()

◆ initialize_()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ peak_top_key()

◆ pop()

◆ push()

◆ push_to_bucket()

◆ reorganize_()

◆ size()

◆ swap_top_bucket()

◆ top()

Member Data Documentation

◆ bucket_map_

◆ buckets_data_

◆ current_bucket_

◆ debug

◆ filled_

◆ insertion_limit_

◆ key_extract_

◆ mins_

◆ num_buckets

◆ num_layers

◆ radix

◆ radix_bits

◆ size_

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