flow::BinaryHeap< T, Compare, Allocator > Class Template Reference

A binary min-heap container. Supports custom comparator and allocator. More...

#include <flow_binary_heap.h>

Public Types
using	value_type = T
using	reference = T&
using	const_reference = const T&
using	pointer = T*
using	const_pointer = const T*
using	iterator = T*
using	const_iterator = const T*
using	difference_type = std::ptrdiff_t
using	container_type = Vector<T, Allocator>
using	allocator_type = container_type::allocator_type

Public Member Functions
constexpr	BinaryHeap () noexcept(noexcept(container_type()) &&noexcept(Compare()))
	Constructs an empty heap with default comparator and allocator. Comparator must be default initializable.
constexpr	BinaryHeap (const allocator_type &allocator) noexcept(noexcept(container_type(allocator)) &&noexcept(Compare()))
	Constructs an empty heap with a specific allocator. Comparator must be default initializable.
constexpr	BinaryHeap (Compare comparator, const allocator_type &allocator={}) noexcept(noexcept(container_type(allocator)) &&noexcept(Compare(std::move(comparator))))
	Constructs an empty heap with a specific allocator.
constexpr	BinaryHeap (const BinaryHeap &)=default
constexpr	BinaryHeap (const BinaryHeap &rhs, const allocator_type &allocator)
constexpr	BinaryHeap (BinaryHeap &&)=default
constexpr	BinaryHeap (BinaryHeap &&rhs, const allocator_type &allocator) noexcept(noexcept(container_type(std::move(rhs.data_), allocator)) &&noexcept(Compare(std::move(rhs.comparator_))))
template<std::input_iterator It>
constexpr	BinaryHeap (It first, It last, Compare comparator={}, const allocator_type &allocator={})
	Iterator range constructor.
constexpr	BinaryHeap (std::initializer_list< T > list, Compare comparator={}, const allocator_type &allocator={})
	Initializer list range constructor.
	~BinaryHeap ()=default
allocator_type	get_allocator () const noexcept
constexpr std::size_t	size () const noexcept
	Return the heap size.
constexpr std::size_t	capacity () const noexcept
	Return the heap capacity.
constexpr bool	empty () const noexcept
	Return true if empty.
const T &	top () const noexcept
	Return the min element.
void	clear () noexcept
	Clear the heap.
void	reserve (std::size_t capacity)
	Reserve the heap capacity.
void	push (const T &value)
	Push the value to the heap.
void	push (T &&value)
	Push the value to the heap.
template<typename ... Args>
void	emplace (Args &&... args)
	Construct the value inplace in the heap.
void	drop () noexcept(std::is_nothrow_move_assignable_v< T >)
	Drop the min element.
T	pop () noexcept(std::is_nothrow_move_constructible_v< T > &&std::is_nothrow_move_assignable_v< T >)
	Pop the min element.

Private Member Functions
std::size_t	fixDownWithHole (std::size_t index) noexcept(std::is_nothrow_move_assignable_v< T >)
void	fixUp (std::size_t index, std::size_t top, T &&value) noexcept(std::is_nothrow_move_assignable_v< T >)
void	heapify () noexcept(std::is_nothrow_move_constructible_v< T > &&std::is_nothrow_move_assignable_v< T >)

Static Private Member Functions
static constexpr bool	hasParent (std::size_t i) noexcept
static constexpr std::size_t	getParent (std::size_t i) noexcept
static constexpr std::size_t	getLeftChild (std::size_t i) noexcept

Private Attributes
container_type	data_
Compare	comparator_

Detailed Description

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>
class flow::BinaryHeap< T, Compare, Allocator >

A binary min-heap container. Supports custom comparator and allocator.

Definition at line 14 of file flow_binary_heap.h.

Member Typedef Documentation

allocator_type

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::allocator_type = container_type::allocator_type

Definition at line 25 of file flow_binary_heap.h.

const_iterator

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::const_iterator = const T*

Definition at line 22 of file flow_binary_heap.h.

const_pointer

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::const_pointer = const T*

Definition at line 20 of file flow_binary_heap.h.

const_reference

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::const_reference = const T&

Definition at line 18 of file flow_binary_heap.h.

container_type

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::container_type = Vector<T, Allocator>

Definition at line 24 of file flow_binary_heap.h.

difference_type

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::difference_type = std::ptrdiff_t

Definition at line 23 of file flow_binary_heap.h.

iterator

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::iterator = T*

Definition at line 21 of file flow_binary_heap.h.

pointer

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::pointer = T*

Definition at line 19 of file flow_binary_heap.h.

reference

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::reference = T&

Definition at line 17 of file flow_binary_heap.h.

value_type

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

using flow::BinaryHeap< T, Compare, Allocator >::value_type = T

Definition at line 16 of file flow_binary_heap.h.

Constructor & Destructor Documentation

BinaryHeap() [1/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( )

inlineconstexprnoexcept

Constructs an empty heap with default comparator and allocator. Comparator must be default initializable.

Definition at line 34 of file flow_binary_heap.h.

      : data_(), comparator_() {
    }

References comparator_, and data_.

Referenced by BinaryHeap(), BinaryHeap(), BinaryHeap(), and BinaryHeap().

BinaryHeap() [2/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( const allocator_type & allocator )

inlineexplicitconstexprnoexcept

Constructs an empty heap with a specific allocator. Comparator must be default initializable.

Definition at line 42 of file flow_binary_heap.h.

      : data_(allocator), comparator_() {
    }

References comparator_, and data_.

BinaryHeap() [3/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( Compare comparator, const allocator_type & allocator = {} )

inlineexplicitconstexprnoexcept

Constructs an empty heap with a specific allocator.

Parameters

comparator	Comparator.
allocator	Memory allocator.

Definition at line 51 of file flow_binary_heap.h.

                                                                                        {})
      noexcept(noexcept(container_type(allocator)) && noexcept(Compare(std::move(comparator))))
      requires !std::default_initializable<Compare>
      : data_(allocator), comparator_(std::move(comparator)) {
    }

BinaryHeap() [4/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( const BinaryHeap< T, Compare, Allocator > & )

constexprdefault

References BinaryHeap().

BinaryHeap() [5/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( const BinaryHeap< T, Compare, Allocator > & rhs, const allocator_type & allocator )

inlineconstexpr

Definition at line 58 of file flow_binary_heap.h.

      : data_(rhs.data_, allocator), comparator_(rhs.comparator_) {
    }

References BinaryHeap(), comparator_, and data_.

BinaryHeap() [6/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( BinaryHeap< T, Compare, Allocator > && )

constexprdefault

References BinaryHeap().

BinaryHeap() [7/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( BinaryHeap< T, Compare, Allocator > && rhs, const allocator_type & allocator )

inlineconstexprnoexcept

Definition at line 63 of file flow_binary_heap.h.

      : data_(std::move(rhs.data_), allocator), comparator_(std::move(rhs.comparator_)) {
    }

References BinaryHeap(), comparator_, and data_.

BinaryHeap() [8/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

template<std::input_iterator It>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( It first, It last, Compare comparator = {}, const allocator_type & allocator = {} )

inlineexplicitconstexpr

Iterator range constructor.

Parameters

first	Iterator to first element.
last	Iterator to one-past-last element.
comp	Comparator.
alloc	Allocator.

Definition at line 74 of file flow_binary_heap.h.

                                                                          {}, const allocator_type& allocator = {})
      : data_(first, last, allocator), comparator_(std::move(comparator)) {
      heapify();
    }

BinaryHeap() [9/9]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::BinaryHeap ( std::initializer_list< T > list, Compare comparator = {}, const allocator_type & allocator = {} )

inlineexplicitconstexpr

Initializer list range constructor.

Parameters

list	Initializer list.
comp	Comparator.
alloc	Allocator.

Definition at line 83 of file flow_binary_heap.h.

                                                                                    {}, const allocator_type& allocator = {})
      : BinaryHeap(list.begin(), list.end(), std::move(comparator), allocator) {
    }

~BinaryHeap()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

flow::BinaryHeap< T, Compare, Allocator >::~BinaryHeap ( )

default

Member Function Documentation

capacity()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::BinaryHeap< T, Compare, Allocator >::capacity ( ) const

inlineconstexprnoexcept

Return the heap capacity.

Returns

The heap capacity.

Definition at line 104 of file flow_binary_heap.h.

                                                  {
      return data_.capacity();
    }

References data_.

Referenced by reserve().

clear()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::clear ( )

inlinenoexcept

Clear the heap.

Definition at line 122 of file flow_binary_heap.h.

                          {
      data_.clear();
    }

References data_.

drop()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::drop ( )

inlinenoexcept

Drop the min element.

Definition at line 154 of file flow_binary_heap.h.

                                                   {
      assert(!data_.empty() && "call drop on an empty heap");
      std::size_t index = fixDownWithHole(0);
      fixUp(index, 0, std::move(data_.back()));
      data_.popBack();
    }

References data_, fixDownWithHole(), and fixUp().

Referenced by pop().

emplace()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

template<typename ... Args>

void flow::BinaryHeap< T, Compare, Allocator >::emplace ( Args &&... args )

inline

Construct the value inplace in the heap.

Parameters

...args

Constructor arguments.

Definition at line 147 of file flow_binary_heap.h.

                                 {
      data_.emplaceBack(std::forward<Args>(args)...);
      T value = std::move(data_.back());
      fixUp(data_.size() - 1, 0, std::move(value));
    }

References data_, and fixUp().

Referenced by push(), and push().

empty()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

bool flow::BinaryHeap< T, Compare, Allocator >::empty ( ) const

inlineconstexprnoexcept

Return true if empty.

Returns

true if empty, otherwise false.

Definition at line 110 of file flow_binary_heap.h.

                                          {
      return data_.empty();
    }

References data_.

fixDownWithHole()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::BinaryHeap< T, Compare, Allocator >::fixDownWithHole ( std::size_t index )

inlineprivatenoexcept

Definition at line 175 of file flow_binary_heap.h.

                                                   {
      for (;;) {
        size_t child = getLeftChild(index);
        if (child >= data_.size()) {
          break;
        }
 
        // Select the less child.
        std::size_t rightChild = child + 1;
        if (rightChild < data_.size() && comparator_(data_[rightChild], data_[child])) {
          child = rightChild;
        }
        data_[index] = std::move(data_[child]);
        index = child;
      }
      return index;
    }

References comparator_, data_, and getLeftChild().

Referenced by drop().

fixUp()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::fixUp ( std::size_t index, std::size_t top, T && value )

inlineprivatenoexcept

Definition at line 195 of file flow_binary_heap.h.

                                                   {
      while (index > top) {
        std::size_t parent = getParent(index);
        if (comparator_(value, data_[parent])) {
          data_[index] = std::move(data_[parent]);
          index = parent;
        } else {
          break;
        }
      }
      data_[index] = std::move(value);
    }

References comparator_, data_, getParent(), and top().

Referenced by drop(), and emplace().

get_allocator()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

allocator_type flow::BinaryHeap< T, Compare, Allocator >::get_allocator ( ) const

inlinenoexcept

Definition at line 90 of file flow_binary_heap.h.

                                                  {
      return data_.get_allocator();
    }

References data_.

getLeftChild()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

constexpr std::size_t flow::BinaryHeap< T, Compare, Allocator >::getLeftChild ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 230 of file flow_binary_heap.h.

                                                                  {
      return i * 2 + 1;
    }

Referenced by fixDownWithHole().

getParent()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

constexpr std::size_t flow::BinaryHeap< T, Compare, Allocator >::getParent ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 225 of file flow_binary_heap.h.

                                                               {
      assert(i > 0 && "calling parent on the root node");
      return (i - 1) / 2;
    }

Referenced by fixUp().

hasParent()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

constexpr bool flow::BinaryHeap< T, Compare, Allocator >::hasParent ( std::size_t i )

inlinestaticconstexprprivatenoexcept

Definition at line 221 of file flow_binary_heap.h.

                                                          {
      return i > 0;
    }

heapify()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::heapify ( )

inlineprivatenoexcept

Definition at line 209 of file flow_binary_heap.h.

                                                                                           {
      if (data_.size() < 2) {
        return;
      }
      for (std::size_t i = data_.size() / 2; i-- > 0 ;) {
        T value = std::move(data_[i]);
        std::size_t hole = fixDownWithHole(i);
        fixUp(hole, i, std::move(value));
      }
    }

References data_.

pop()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

T flow::BinaryHeap< T, Compare, Allocator >::pop ( )

inlinenoexcept

Pop the min element.

Returns

The min element.

Definition at line 164 of file flow_binary_heap.h.

                                                                                            {
      assert(!data_.empty() && "call pop on an empty heap");
      T value = std::move(data_.front());
      drop();
      return value;
    }

References data_, and drop().

push() [1/2]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::push ( const T & value )

inline

Push the value to the heap.

Parameters

value

Definition at line 134 of file flow_binary_heap.h.

                              {
      emplace(value);
    }

References emplace().

push() [2/2]

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::push ( T && value )

inline

Push the value to the heap.

Parameters

value

Definition at line 140 of file flow_binary_heap.h.

                         {
      emplace(std::move(value));
    }

References emplace().

reserve()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

void flow::BinaryHeap< T, Compare, Allocator >::reserve ( std::size_t capacity )

inline

Reserve the heap capacity.

Parameters

capacity

Definition at line 128 of file flow_binary_heap.h.

                                     {
      data_.reserve(capacity);
    }

References capacity(), and data_.

size()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

std::size_t flow::BinaryHeap< T, Compare, Allocator >::size ( ) const

inlineconstexprnoexcept

Return the heap size.

Returns

The heap size.

Definition at line 98 of file flow_binary_heap.h.

                                              {
      return data_.size();
    }

References data_.

top()

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

const T & flow::BinaryHeap< T, Compare, Allocator >::top ( ) const

inlinenoexcept

Return the min element.

Returns

The min element.

Definition at line 116 of file flow_binary_heap.h.

                                  {
      assert(!data_.empty() && "call top on an empty heap");
      return data_.front();
    }

References data_.

Referenced by fixUp().

Member Data Documentation

comparator_

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

Compare flow::BinaryHeap< T, Compare, Allocator >::comparator_

private

Definition at line 29 of file flow_binary_heap.h.

Referenced by BinaryHeap(), BinaryHeap(), BinaryHeap(), BinaryHeap(), fixDownWithHole(), and fixUp().

data_

template<typename T, typename Compare = std::less<T>, typename Allocator = PolymorphicAllocator<T>>

container_type flow::BinaryHeap< T, Compare, Allocator >::data_

private

Definition at line 28 of file flow_binary_heap.h.

Referenced by BinaryHeap(), BinaryHeap(), BinaryHeap(), BinaryHeap(), capacity(), clear(), drop(), emplace(), empty(), fixDownWithHole(), fixUp(), get_allocator(), heapify(), pop(), reserve(), size(), and top().

---

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

• flow_binary_heap.h