A priority queue implemented as a binary heap. More...

#include <binary_heap.h>

Public Types
typedef T *	iterator

typedef const T *	const_iterator

typedef std::reverse_iterator< T * >	reverse_iterator

typedef std::reverse_iterator< const T * >	const_reverse_iterator

Public Member Functions
	binary_heap (const Comp &comp=Comp()) noexcept
	Construct the binary heap with the given comparator. More...

	binary_heap (const Alloc &allocator, const Comp &comp=Comp()) noexcept
	Construct the binary heap with the given allocator and comparator. More...

	binary_heap (size_t capacity, const Comp &comp=Comp()) noexcept
	Construct the binary heap with the given comparator and an initial capacity. More...

	binary_heap (size_t capacity, const Alloc &allocator, const Comp &comp=Comp()) noexcept
	Construct the binary heap with the given allocator, comparator and an initial capacity. More...

	binary_heap (std::initializer_list< T > initializer, const Comp &comp=Comp())
	Construct the binary heap with the given comparator and an initial set of values. More...

	binary_heap (std::initializer_list< T > initializer, const Alloc &allocator, const Comp &comp=Comp())
	Construct the binary heap with the given allocator, comparator and an initial set of values. More...

	binary_heap (const binary_heap &other) noexcept(std::is_nothrow_copy_constructible_v< T >)

	binary_heap (binary_heap &&other) noexcept(std::is_nothrow_move_constructible_v< T >)

	binary_heap (const binary_heap &other, const Alloc &allocator) noexcept(std::is_nothrow_copy_constructible_v< T >)

	binary_heap (binary_heap &&other, const Alloc &allocator) noexcept(std::is_nothrow_move_constructible_v< T >)

	~binary_heap ()

binary_heap &	operator= (const binary_heap &other) noexcept(std::is_nothrow_copy_assignable_v< T >)

binary_heap &	operator= (binary_heap &&other) noexcept(std::is_nothrow_move_assignable_v< T >)

iterator	begin () noexcept

const_iterator	begin () const noexcept

iterator	end () noexcept

const_iterator	end () const noexcept

reverse_iterator	rbegin () noexcept

const_reverse_iterator	rbegin () const noexcept

reverse_iterator	rend () noexcept

const_reverse_iterator	rend () const noexcept

iterator	data () noexcept
	Returns an iterator to the start of the heap. More...

const_iterator	data () const noexcept
	Returns a const iterator to the start of the heap. More...

size_t	size () const noexcept
	Returns the current size of the heap. More...

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

bool	empty () const noexcept
	Returns true if the heap has no elements. More...

void	reserve (size_t n) noexcept
	Reserves the capacity of the heap to `n`, without initializing any elements. More...

template<typename V >
iterator	insert (V &&value) noexcept
	Inserts a new element into the heap via perfect forwarding. More...

T &	peek () noexcept
	Peeks at the root element (lowest or highest, depending on min or max heap) and returns a reference to it. More...

T	pop () noexcept
	Removes the root element (lowest or highest, depending on min or max heap) and returns it. More...

iterator	find (const T &value) const noexcept
	Returns an iterator to the element `index`. Takes O(n) time. More...

void	clear () noexcept
	Clear all elements in the heap, destroying each element. More...

Detailed Description

template<typename T, typename Comp, typename Alloc>
class ktl::binary_heap< T, Comp, Alloc >

A priority queue implemented as a binary heap.

Template Parameters

T	The type to use. Must be move constructible and move assignable
Comp	The comparison function. Usually std::greater<T> or std::less<T>
Alloc	The type of allocoator to use

Member Typedef Documentation

◆ const_iterator

template<typename T , typename Comp , typename Alloc >

typedef const T* ktl::binary_heap< T, Comp, Alloc >::const_iterator

◆ const_reverse_iterator

template<typename T , typename Comp , typename Alloc >

typedef std::reverse_iterator<const T*> ktl::binary_heap< T, Comp, Alloc >::const_reverse_iterator

◆ iterator

template<typename T , typename Comp , typename Alloc >

typedef T* ktl::binary_heap< T, Comp, Alloc >::iterator

◆ reverse_iterator

template<typename T , typename Comp , typename Alloc >

typedef std::reverse_iterator<T*> ktl::binary_heap< T, Comp, Alloc >::reverse_iterator

Constructor & Destructor Documentation

◆ binary_heap() [1/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap ( const Comp & comp = Comp() )

inlinenoexcept

Construct the binary heap with the given comparator.

Parameters

comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [2/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	const Alloc &	allocator,
		const Comp &	comp = `Comp()`
	)

inlinenoexcept

Construct the binary heap with the given allocator and comparator.

Parameters

allocator	The allocator to use
comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [3/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	size_t	capacity,
		const Comp &	comp = `Comp()`
	)

inlineexplicitnoexcept

Construct the binary heap with the given comparator and an initial capacity.

Parameters

capacity	The initial capacity to use
comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [4/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	size_t	capacity,
		const Alloc &	allocator,
		const Comp &	comp = `Comp()`
	)

inlineexplicitnoexcept

Construct the binary heap with the given allocator, comparator and an initial capacity.

Parameters

capacity	The initial capacity to use
allocator	The allocator to use. Will be default constructed if unspecified
comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [5/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	std::initializer_list< T >	initializer,
		const Comp &	comp = `Comp()`
	)

inline

Construct the binary heap with the given comparator and an initial set of values.

Parameters

initializer	A list of values to insert into the binary heap
comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [6/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	std::initializer_list< T >	initializer,
		const Alloc &	allocator,
		const Comp &	comp = `Comp()`
	)

inline

Construct the binary heap with the given allocator, comparator and an initial set of values.

Parameters

initializer	A list of values to insert into the binary heap
allocator	The allocator to use. Will be default constructed if unspecified
comp	The comparator to use. Will be default constructed if unspecified

◆ binary_heap() [7/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap ( const binary_heap< T, Comp, Alloc > & other )

inlinenoexcept

◆ binary_heap() [8/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap ( binary_heap< T, Comp, Alloc > && other )

inlinenoexcept

◆ binary_heap() [9/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	const binary_heap< T, Comp, Alloc > &	other,
		const Alloc &	allocator
	)

inlinenoexcept

◆ binary_heap() [10/10]

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::binary_heap	(	binary_heap< T, Comp, Alloc > &&	other,
		const Alloc &	allocator
	)

inlinenoexcept

◆ ~binary_heap()

template<typename T , typename Comp , typename Alloc >

ktl::binary_heap< T, Comp, Alloc >::~binary_heap ( )

inline

Member Function Documentation

◆ begin() [1/2]

template<typename T , typename Comp , typename Alloc >

const_iterator ktl::binary_heap< T, Comp, Alloc >::begin ( ) const

inlinenoexcept

◆ begin() [2/2]

template<typename T , typename Comp , typename Alloc >

iterator ktl::binary_heap< T, Comp, Alloc >::begin ( )

inlinenoexcept

◆ capacity()

template<typename T , typename Comp , typename Alloc >

size_t ktl::binary_heap< T, Comp, Alloc >::capacity ( ) const

inlinenoexcept

Returns the current capacity of the heap.

Returns: The current capacity of the heap in number of elements.

◆ clear()

template<typename T , typename Comp , typename Alloc >

void ktl::binary_heap< T, Comp, Alloc >::clear ( )

inlinenoexcept

Clear all elements in the heap, destroying each element.

◆ data() [1/2]

template<typename T , typename Comp , typename Alloc >

const_iterator ktl::binary_heap< T, Comp, Alloc >::data ( ) const

inlinenoexcept

Returns a const iterator to the start of the heap.

Returns: A const iterator to the start of the heap.

◆ data() [2/2]

template<typename T , typename Comp , typename Alloc >

iterator ktl::binary_heap< T, Comp, Alloc >::data ( )

inlinenoexcept

Returns an iterator to the start of the heap.

Returns: An iterator to the start of the heap.

◆ empty()

template<typename T , typename Comp , typename Alloc >

bool ktl::binary_heap< T, Comp, Alloc >::empty ( ) const

inlinenoexcept

Returns true if the heap has no elements.

Returns: Whether the heap has a size of 0.

◆ end() [1/2]

template<typename T , typename Comp , typename Alloc >

const_iterator ktl::binary_heap< T, Comp, Alloc >::end ( ) const

inlinenoexcept

◆ end() [2/2]

template<typename T , typename Comp , typename Alloc >

iterator ktl::binary_heap< T, Comp, Alloc >::end ( )

inlinenoexcept

◆ find()

template<typename T , typename Comp , typename Alloc >

iterator ktl::binary_heap< T, Comp, Alloc >::find ( const T & value ) const

inlinenoexcept

Returns an iterator to the element index. Takes O(n) time.

Parameters

value The value to return the iterator of.

Returns: An iterator to the given value or end() if not found.

◆ insert()

template<typename T , typename Comp , typename Alloc >

template<typename V >

iterator ktl::binary_heap< T, Comp, Alloc >::insert ( V && value )

inlinenoexcept

Inserts a new element into the heap via perfect forwarding.

Template Parameters

V	The type to insert.

Parameters

value The element to insert into the heap.

Returns: An iterator to the element that was added.

◆ operator=() [1/2]

template<typename T , typename Comp , typename Alloc >

binary_heap& ktl::binary_heap< T, Comp, Alloc >::operator= ( binary_heap< T, Comp, Alloc > && other )

inlinenoexcept

◆ operator=() [2/2]

template<typename T , typename Comp , typename Alloc >

binary_heap& ktl::binary_heap< T, Comp, Alloc >::operator= ( const binary_heap< T, Comp, Alloc > & other )

inlinenoexcept

◆ peek()

template<typename T , typename Comp , typename Alloc >

T& ktl::binary_heap< T, Comp, Alloc >::peek ( )

inlinenoexcept

Peeks at the root element (lowest or highest, depending on min or max heap) and returns a reference to it.

Returns: A reference to the root element.

◆ pop()

template<typename T , typename Comp , typename Alloc >

T ktl::binary_heap< T, Comp, Alloc >::pop ( )

inlinenoexcept

Removes the root element (lowest or highest, depending on min or max heap) and returns it.

Returns: The removed root element, returned by value.

◆ rbegin() [1/2]

template<typename T , typename Comp , typename Alloc >

const_reverse_iterator ktl::binary_heap< T, Comp, Alloc >::rbegin ( ) const

inlinenoexcept

◆ rbegin() [2/2]

template<typename T , typename Comp , typename Alloc >

reverse_iterator ktl::binary_heap< T, Comp, Alloc >::rbegin ( )

inlinenoexcept

◆ rend() [1/2]

template<typename T , typename Comp , typename Alloc >

const_reverse_iterator ktl::binary_heap< T, Comp, Alloc >::rend ( ) const

inlinenoexcept

◆ rend() [2/2]

template<typename T , typename Comp , typename Alloc >

reverse_iterator ktl::binary_heap< T, Comp, Alloc >::rend ( )

inlinenoexcept

◆ reserve()

template<typename T , typename Comp , typename Alloc >

void ktl::binary_heap< T, Comp, Alloc >::reserve ( size_t n )

inlinenoexcept

Reserves the capacity of the heap to n, without initializing any elements.

Parameters

n	The minimum capacity of the heap.

◆ size()

template<typename T , typename Comp , typename Alloc >

size_t ktl::binary_heap< T, Comp, Alloc >::size ( ) const

inlinenoexcept

Returns the current size of the heap.

Returns: The current size of the heap in number of elements.

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

include/ktl/containers/binary_heap.h

Public Types

Public Member Functions

Detailed Description

template<typename T, typename Comp, typename Alloc> class ktl::binary_heap< T, Comp, Alloc >

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ binary_heap() [1/10]

◆ binary_heap() [2/10]

◆ binary_heap() [3/10]

◆ binary_heap() [4/10]

◆ binary_heap() [5/10]

◆ binary_heap() [6/10]

◆ binary_heap() [7/10]

◆ binary_heap() [8/10]

◆ binary_heap() [9/10]

◆ binary_heap() [10/10]

◆ ~binary_heap()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ clear()

◆ data() [1/2]

◆ data() [2/2]

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ find()

◆ insert()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ peek()

◆ pop()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ reserve()

◆ size()

template<typename T, typename Comp, typename Alloc>
class ktl::binary_heap< T, Comp, Alloc >