Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

Private Types

using Bucket = RadixHeapNode< V, P > *
 

Private Member Functions

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

Static Private Member Functions

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

Private Attributes

m_bucketMask
 Priority of the lowest element so far. More...
 
std::array< Bucket, BITS+1 > m_buckets
 Mask describing state of buckets (for fast lookup). More...
 
m_minimum
 Number of elements. More...
 
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
VDenotes type of values of inserted elements.
PDenotes type of integral priorities of inserted elements.

Definition at line 74 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 110 of file RadixHeap.h.

Constructor & Destructor Documentation

◆ RadixHeap()

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

Creates empty heap.

Definition at line 153 of file RadixHeap.h.

◆ ~RadixHeap()

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

Destructs the heap.

Definition at line 161 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 105 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 246 of file RadixHeap.h.

◆ msbSet()

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

Returns most significant bit set on given mask.

Definition at line 124 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 186 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
valueA value of inserted element.
priorityA priority of inserted element.
Returns
Handle to the inserted node.

Definition at line 175 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 100 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 111 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 116 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 117 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 115 of file RadixHeap.h.

◆ m_size

template<typename V , typename P >
std::size_t ogdf::RadixHeap< V, P >::m_size
private

Definition at line 113 of file RadixHeap.h.


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