Template Class RadixHeap

Nested Relationships

Nested Types

Class Documentation

template<class T, std::integral K = std::uint32_t, unsigned B = 4>
class RadixHeap

a monotone queue of items with integer keys K, the least key first, in buckets by digits of B bits

Public Types

using Item = T

the type of the items

using Key = K

the type of the keys

Public Functions

void push(const T &x, K k)

pushes x with the key k

Pre:

k is not smaller than the last key extracted or read by top() and topKey() (any key before the first of them and after clear())

const T &top(void)

an item of least key, the last pushed among those

Pre:

the queue is not empty

K topKey(void)

the least key

Pre:

the queue is not empty

K peekKey(void) const

the least key, read from the least key of the first bucket in use, which does not move the buckets: the keys pushed next need only be not smaller than the last one extracted, as if topKey() were not called

Pre:

the queue is not empty

T pop(void)

removes top() and returns it

Pre:

the queue is not empty

template<class F>
void extractBelow(K limit, F &&f)

removes the items of keys below limit, calling f( item , key ) for each of them in no given order, which count as extracted: the buckets whose keys are all below limit are emptied whole, with no move, and the first one that holds a key not below it is moved to the rows below for its least key, as by pop(), until the limit falls between two buckets or within one of the row 0

inline bool empty(void) const
inline std::size_t size(void) const
void clear(void)

removes the items, the buckets keeping their memory; any key may be pushed next