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.

#include <d_ary_heap.hpp>

Public Types
using	compare_type = Compare

using	key_type = KeyType

Public Member Functions
	DAryHeap (compare_type cmp=compare_type())
	Allocates an empty heap. More...

	DAryHeap (const DAryHeap &)=default
	Copy. More...

	DAryHeap (DAryHeap &&)=default
	Move. 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...

size_t	capacity () const noexcept
	Returns the capacity of the heap. More...

void	clear ()
	Empties the heap. More...

bool	empty () const noexcept
	Returns true if the heap has no items, false otherwise. More...

key_type	extract_top ()
	Removes and returns the top item. More...

DAryHeap &	operator= (const DAryHeap &)=default

DAryHeap &	operator= (DAryHeap &&)=default

void	pop ()
	Removes the top item. More...

void	push (const key_type &new_key)
	Inserts a new item. More...

void	push (key_type &&new_key)
	Inserts a new item. More...

void	reserve (size_t new_size)
	Allocates space for `new_size` items. More...

bool	sanity_check ()

size_t	size () const noexcept
	Returns the number of items in the heap. More...

const key_type &	top () const noexcept
	Returns the top item. More...

void	update_all ()
	Rebuilds the heap. More...

Static Public Attributes
static constexpr size_t	arity = Arity

Protected Attributes
compare_type	cmp_
	Compare function. More...

std::vector< key_type >	heap_
	Cells in the heap. More...

Private Member Functions
void	heapify ()
	Reorganize heap_ into a heap. More...

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_down (size_t k)

void	sift_up (size_t k)

Member Typedef Documentation

◆ compare_type

using compare_type = Compare

Definition at line 43 of file d_ary_heap.hpp.

◆ key_type

using key_type = KeyType

Definition at line 42 of file d_ary_heap.hpp.

Constructor & Destructor Documentation

◆ DAryHeap() [1/3]

DAryHeap ( compare_type cmp = compare_type() )

inlineexplicit

Allocates an empty heap.

Definition at line 56 of file d_ary_heap.hpp.

Referenced by DAryHeap< KeyType, Arity, Compare >::reserve().

◆ DAryHeap() [2/3]

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

default

Copy.

◆ DAryHeap() [3/3]

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

default

Move.

Member Function Documentation

◆ build_heap() [1/3]

void build_heap	(	InputIterator	first,
		InputIterator	last
	)

inline

Builds a heap from a container.

Definition at line 129 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::heapify().

◆ build_heap() [2/3]

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.

References DAryHeap< KeyType, Arity, Compare >::heapify().

◆ build_heap() [3/3]

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.

References DAryHeap< KeyType, Arity, Compare >::empty(), and DAryHeap< KeyType, Arity, Compare >::heapify().

◆ capacity()

size_t capacity ( ) const

inlinenoexcept

Returns the capacity of the heap.

Definition at line 81 of file d_ary_heap.hpp.

◆ clear()

void clear ( )

inline

Empties the heap.

Definition at line 73 of file d_ary_heap.hpp.

◆ empty()

bool empty ( ) const

inlinenoexcept

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

Definition at line 84 of file d_ary_heap.hpp.

Referenced by DAryHeap< KeyType, Arity, Compare >::build_heap(), DAryHeap< KeyType, Arity, Compare >::pop(), DAryHeap< KeyType, Arity, Compare >::sanity_check(), and DAryHeap< KeyType, Arity, Compare >::top().

◆ extract_top()

key_type extract_top ( )

inline

Removes and returns the top item.

Definition at line 116 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::pop(), and DAryHeap< KeyType, Arity, Compare >::top().

◆ heapify()

void heapify ( )

inlineprivate

Reorganize heap_ into a heap.

Definition at line 224 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::cmp_, DAryHeap< KeyType, Arity, Compare >::left(), and gen_data::value.

Referenced by DAryHeap< KeyType, Arity, Compare >::build_heap(), and DAryHeap< KeyType, Arity, Compare >::update_all().

◆ left()

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.

Referenced by DAryHeap< KeyType, Arity, Compare >::heapify(), DAryHeap< KeyType, Arity, Compare >::sanity_check(), and DAryHeap< KeyType, Arity, Compare >::sift_down().

◆ operator=() [1/2]

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

default

Referenced by DAryHeap< KeyType, Arity, Compare >::reserve().

◆ operator=() [2/2]

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

default

◆ parent()

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.

References DAryHeap< KeyType, Arity, Compare >::arity.

Referenced by DAryHeap< KeyType, Arity, Compare >::sift_up().

◆ pop()

void pop ( )

inline

Removes the top item.

Definition at line 107 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::empty(), DAryHeap< KeyType, Arity, Compare >::sift_down(), and tlx::swap().

Referenced by DAryHeap< KeyType, Arity, Compare >::extract_top().

◆ push() [1/2]

void push ( const key_type & new_key )

inline

Inserts a new item.

Definition at line 87 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::sift_up().

◆ push() [2/2]

void push ( key_type && new_key )

inline

Inserts a new item.

Definition at line 94 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::sift_up().

◆ reserve()

void reserve ( size_t new_size )

inline

Allocates space for new_size items.

Definition at line 60 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::DAryHeap(), and DAryHeap< KeyType, Arity, Compare >::operator=().

◆ sanity_check()

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.

References DAryHeap< KeyType, Arity, Compare >::cmp_, DAryHeap< KeyType, Arity, Compare >::empty(), and DAryHeap< KeyType, Arity, Compare >::left().

◆ sift_down()

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.

References DAryHeap< KeyType, Arity, Compare >::arity, DAryHeap< KeyType, Arity, Compare >::cmp_, DAryHeap< KeyType, Arity, Compare >::left(), min(), and gen_data::value.

Referenced by DAryHeap< KeyType, Arity, Compare >::pop().

◆ sift_up()

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.

References DAryHeap< KeyType, Arity, Compare >::cmp_, DAryHeap< KeyType, Arity, Compare >::parent(), and gen_data::value.

Referenced by DAryHeap< KeyType, Arity, Compare >::push().

◆ size()

size_t size ( ) const

inlinenoexcept

Returns the number of items in the heap.

Definition at line 78 of file d_ary_heap.hpp.

◆ top()

const key_type& top ( ) const

inlinenoexcept

Returns the top item.

Definition at line 101 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::empty().

Referenced by DAryHeap< KeyType, Arity, Compare >::extract_top().

◆ update_all()

void update_all ( )

inline

Rebuilds the heap.

Definition at line 123 of file d_ary_heap.hpp.

References DAryHeap< KeyType, Arity, Compare >::heapify().

Member Data Documentation

◆ arity

constexpr size_t arity = Arity

static

Definition at line 45 of file d_ary_heap.hpp.

Referenced by DAryHeap< KeyType, Arity, Compare >::parent(), and DAryHeap< KeyType, Arity, Compare >::sift_down().

◆ cmp_

compare_type cmp_

protected

Compare function.

Definition at line 52 of file d_ary_heap.hpp.

Referenced by DAryHeap< KeyType, Arity, Compare >::heapify(), DAryHeap< KeyType, Arity, Compare >::sanity_check(), DAryHeap< KeyType, Arity, Compare >::sift_down(), and DAryHeap< KeyType, Arity, Compare >::sift_up().

◆ heap_

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:

extlib/tlx/tlx/container/d_ary_heap.hpp

Detailed Description

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

Public Types

Public Member Functions

Static Public Attributes

Protected Attributes

Private Member Functions

Member Typedef Documentation

◆ compare_type

◆ key_type

Constructor & Destructor Documentation

◆ DAryHeap() [1/3]

◆ DAryHeap() [2/3]

◆ DAryHeap() [3/3]

Member Function Documentation

◆ build_heap() [1/3]

◆ build_heap() [2/3]

◆ build_heap() [3/3]

◆ capacity()

◆ clear()

◆ empty()

◆ extract_top()

◆ heapify()

◆ left()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parent()

◆ pop()

◆ push() [1/2]

◆ push() [2/2]

◆ reserve()

◆ sanity_check()

◆ sift_down()

◆ sift_up()

◆ size()

◆ top()

◆ update_all()

Member Data Documentation

◆ arity

◆ cmp_

◆ heap_

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