ogdf::RadixHeap< V, P > Class Template Reference

Radix heap data structure implementation. More...

#include <ogdf/basic/heap/RadixHeap.h>

Public Member Functions
	RadixHeap ()
	Creates empty heap.
	~RadixHeap ()
	Destructs the heap.
bool	empty () const
	Checks whether the heap is empty.
V	pop ()
	Removes the top element from the heap and returns its value.
RadixHeapNode< V, P > *	push (const V &value, const P &priority)
	Inserts a new node with given value and priority into a heap.
std::size_t	size () const
	Number of elements contained within the heap.

Private Types
using	Bucket = RadixHeapNode< V, P > *

Private Member Functions
void	insert (RadixHeapNode< V, P > *heapNode)
	Buckets with values.

Static Private Member Functions
template<typename T >
static std::size_t	msbSet (T mask)
	Returns most significant bit set on given mask.

Private Attributes
P	m_bucketMask
	Priority of the lowest element so far.
std::array< Bucket, BITS+1 >	m_buckets
	Mask describing state of buckets (for fast lookup).
P	m_minimum
	Number of elements.
std::size_t	m_size

Static Private Attributes
static constexpr std::size_t	BITS = sizeof(P) * 8

Detailed Description

template<typename V, typename P>
class ogdf::RadixHeap< V, P >

Radix heap data structure implementation.

It is just a simple implementation of the idea sketched here: http://ssp.impulsetrain.com/radix-heap.html

To achieve best performance it also uses low-level word functions where avaliable.

Template Parameters

V	Denotes type of values of inserted elements.
P	Denotes type of integral priorities of inserted elements.

Definition at line 69 of file RadixHeap.h.

Member Typedef Documentation

Bucket

template<typename V , typename P >

using ogdf::RadixHeap< V, P >::Bucket = RadixHeapNode<V, P>*

private

Definition at line 101 of file RadixHeap.h.

Constructor & Destructor Documentation

RadixHeap()

template<typename V , typename P >

ogdf::RadixHeap< V, P >::RadixHeap

(

)

Creates empty heap.

Definition at line 142 of file RadixHeap.h.

~RadixHeap()

template<typename V , typename P >

ogdf::RadixHeap< V, P >::~RadixHeap

(

)

Destructs the heap.

Definition at line 147 of file RadixHeap.h.

Member Function Documentation

empty()

template<typename V , typename P >

bool ogdf::RadixHeap< V, P >::empty ( ) const

inline

Checks whether the heap is empty.

Definition at line 98 of file RadixHeap.h.

insert()

template<typename V , typename P >

void ogdf::RadixHeap< V, P >::insert ( RadixHeapNode< V, P > *  heapNode )

inlineprivate

Buckets with values.

Inserts heapNode to the appropriate bucket.

Definition at line 226 of file RadixHeap.h.

msbSet()

template<typename V , typename P >

template<typename T >

static std::size_t ogdf::RadixHeap< V, P >::msbSet ( T  mask )

inlinestaticprivate

Returns most significant bit set on given mask.

Definition at line 115 of file RadixHeap.h.

pop()

template<typename V , typename P >

V ogdf::RadixHeap< V, P >::pop

(

)

Removes the top element from the heap and returns its value.

Behaviour of this function is undefined if the heap is empty.

Returns

Value of the popped node.

Definition at line 168 of file RadixHeap.h.

push()

template<typename V , typename P >

RadixHeapNode< V, P > * ogdf::RadixHeap< V, P >::push	(	const V &	value,
		const P &	priority
	)

Inserts a new node with given value and priority into a heap.

Parameters

value	A value of inserted element.
priority	A priority of inserted element.

Returns

Handle to the inserted node.

Definition at line 159 of file RadixHeap.h.

size()

template<typename V , typename P >

std::size_t ogdf::RadixHeap< V, P >::size ( ) const

inline

Number of elements contained within the heap.

Definition at line 95 of file RadixHeap.h.

Member Data Documentation

BITS

template<typename V , typename P >

constexpr std::size_t ogdf::RadixHeap< V, P >::BITS = sizeof(P) * 8

staticconstexprprivate

Definition at line 102 of file RadixHeap.h.

m_bucketMask

template<typename V , typename P >

P ogdf::RadixHeap< V, P >::m_bucketMask

private

Priority of the lowest element so far.

Definition at line 107 of file RadixHeap.h.

m_buckets

template<typename V , typename P >

std::array<Bucket, BITS + 1> ogdf::RadixHeap< V, P >::m_buckets

private

Mask describing state of buckets (for fast lookup).

Definition at line 108 of file RadixHeap.h.

m_minimum

template<typename V , typename P >

P ogdf::RadixHeap< V, P >::m_minimum

private

Number of elements.

Definition at line 106 of file RadixHeap.h.

m_size

template<typename V , typename P >

std::size_t ogdf::RadixHeap< V, P >::m_size

private

Definition at line 104 of file RadixHeap.h.

---

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

• include/ogdf/basic/heap/RadixHeap.h