DAryHeap< KeyType, Arity, Compare > Class Template Reference

This class implements a d-ary comparison-based heap usable as a priority queue. More...

#include <d_ary_heap.hpp>

Public Types
using	key_type = KeyType
using	compare_type = Compare

Public Member Functions
	DAryHeap (compare_type cmp=compare_type())
	Allocates an empty heap. More...
void	reserve (size_t new_size)
	Allocates space for new_size items. More...
	DAryHeap (const DAryHeap &)=default
	Copy. More...
DAryHeap &	operator= (const DAryHeap &)=default
	DAryHeap (DAryHeap &&)=default
	Move. More...
DAryHeap &	operator= (DAryHeap &&)=default
void	clear ()
	Empties the heap. More...
size_t	size () const noexcept
	Returns the number of items in the heap. More...
size_t	capacity () const noexcept
	Returns the capacity of the heap. More...
bool	empty () const noexcept
	Returns true if the heap has no items, false otherwise. More...
void	push (const key_type &new_key)
	Inserts a new item. More...
void	push (key_type &&new_key)
	Inserts a new item. More...
const key_type &	top () const noexcept
	Returns the top item. More...
void	pop ()
	Removes the top item. More...
key_type	extract_top ()
	Removes and returns the top item. More...
void	update_all ()
	Rebuilds the heap. More...
template<class InputIterator >
void	build_heap (InputIterator first, InputIterator last)
	Builds a heap from a container. More...
void	build_heap (const std::vector< key_type > &keys)
	Builds a heap from the vector keys. Items of keys are copied. More...
void	build_heap (std::vector< key_type > &&keys)
	Builds a heap from the vector keys. Items of keys are moved. More...
bool	sanity_check ()
	For debugging: runs a BFS from the root node and verifies that the heap property is respected. More...

Static Public Attributes
static constexpr size_t	arity

Protected Attributes
std::vector< key_type >	heap_
	Cells in the heap. More...
compare_type	cmp_
	Compare function. More...

Private Member Functions
size_t	left (size_t k) const
	Returns the position of the left child of the node at position k. More...
size_t	parent (size_t k) const
	Returns the position of the parent of the node at position k. More...
void	sift_up (size_t k)
	Pushes the node at position k up until either it becomes the root or its parent has lower or equal priority. More...
void	sift_down (size_t k)
	Pushes the item at position k down until either it becomes a leaf or all its children have higher priority. More...
void	heapify ()
	Reorganize heap_ into a heap. More...

Detailed Description

template<typename KeyType, unsigned Arity = 2, typename Compare = std::less<KeyType>>
class tlx::DAryHeap< KeyType, Arity, Compare >

This class implements a d-ary comparison-based heap usable as a priority queue.

Higher arity yields better cache efficiency.

Template Parameters

KeyType	Key type.
Arity	A positive integer.
Compare	Function object to order keys.

Definition at line 37 of file d_ary_heap.hpp.

Member Typedef Documentation

using compare_type = Compare

Definition at line 43 of file d_ary_heap.hpp.

using key_type = KeyType

Definition at line 42 of file d_ary_heap.hpp.

Constructor & Destructor Documentation

DAryHeap ( compare_type  cmp = compare_type() )

inlineexplicit

Allocates an empty heap.

Definition at line 56 of file d_ary_heap.hpp.

DAryHeap ( const DAryHeap< KeyType, Arity, Compare > &  )

default

Copy.

DAryHeap ( DAryHeap< KeyType, Arity, Compare > &&  )

default

Move.

Member Function Documentation

void build_heap ( InputIterator  first, InputIterator  last  )

inline

Builds a heap from a container.

Definition at line 129 of file d_ary_heap.hpp.

void build_heap ( const std::vector< key_type > &  keys )

inline

Builds a heap from the vector keys. Items of keys are copied.

Definition at line 135 of file d_ary_heap.hpp.

void build_heap ( std::vector< key_type > &&  keys )

inline

Builds a heap from the vector keys. Items of keys are moved.

Definition at line 142 of file d_ary_heap.hpp.

size_t capacity ( ) const

inlinenoexcept

Returns the capacity of the heap.

Definition at line 81 of file d_ary_heap.hpp.

void clear ( )

inline

Empties the heap.

Definition at line 73 of file d_ary_heap.hpp.

bool empty ( ) const

inlinenoexcept

Returns true if the heap has no items, false otherwise.

Definition at line 84 of file d_ary_heap.hpp.

key_type extract_top ( )

inline

Removes and returns the top item.

Definition at line 116 of file d_ary_heap.hpp.

void heapify ( )

inlineprivate

Reorganize heap_ into a heap.

Definition at line 224 of file d_ary_heap.hpp.

size_t left ( size_t  k ) const

inlineprivate

Returns the position of the left child of the node at position k.

Definition at line 175 of file d_ary_heap.hpp.

DAryHeap& operator= ( const DAryHeap< KeyType, Arity, Compare > &  )

default

DAryHeap& operator= ( DAryHeap< KeyType, Arity, Compare > &&  )

default

size_t parent ( size_t  k ) const

inlineprivate

Returns the position of the parent of the node at position k.

Definition at line 178 of file d_ary_heap.hpp.

void pop ( )

inline

Removes the top item.

Definition at line 107 of file d_ary_heap.hpp.

void push ( const key_type &  new_key )

inline

Inserts a new item.

Definition at line 87 of file d_ary_heap.hpp.

void push ( key_type &&  new_key )

inline

Inserts a new item.

Definition at line 94 of file d_ary_heap.hpp.

void reserve ( size_t  new_size )

inline

Allocates space for new_size items.

Definition at line 60 of file d_ary_heap.hpp.

bool sanity_check ( )

inline

For debugging: runs a BFS from the root node and verifies that the heap property is respected.

Definition at line 151 of file d_ary_heap.hpp.

void sift_down ( size_t  k )

inlineprivate

Pushes the item at position k down until either it becomes a leaf or all its children have higher priority.

Definition at line 194 of file d_ary_heap.hpp.

void sift_up ( size_t  k )

inlineprivate

Pushes the node at position k up until either it becomes the root or its parent has lower or equal priority.

Definition at line 182 of file d_ary_heap.hpp.

size_t size ( ) const

inlinenoexcept

Returns the number of items in the heap.

Definition at line 78 of file d_ary_heap.hpp.

const key_type& top ( ) const

inlinenoexcept

Returns the top item.

Definition at line 101 of file d_ary_heap.hpp.

void update_all ( )

inline

Rebuilds the heap.

Definition at line 123 of file d_ary_heap.hpp.

Member Data Documentation

constexpr size_t arity

static

Definition at line 45 of file d_ary_heap.hpp.

compare_type cmp_

protected

Compare function.

Definition at line 52 of file d_ary_heap.hpp.

std::vector<key_type> heap_

protected

Cells in the heap.

Definition at line 49 of file d_ary_heap.hpp.

---

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

• tlx/container/d_ary_heap.hpp