cplib::DaryHeap< T, Comp, D > Struct Template Reference

D-ary heap, slightly faster than binary heap due to less random memory access. More...

#include <dary_heap.hpp>

Public Types
using	size_type = std::size_t

Public Member Functions
size_type	size () const
	Returns the number of elements.
bool	empty () const
	Returns whether the heap is empty.
const T &	top ()
	Returns the top element.
void	push (const T &t)
	Insert an element into the heap.
void	push (T &&t)
	Insert an element into the heap.
template<typename... Args>
void	emplace (Args &&... args)
	Construct a new element in place in the heap.
void	pop ()
	Remove the top element from the heap.

Detailed Description

template<typename T, typename Comp = std::less<T>, int D = 8>
struct cplib::DaryHeap< T, Comp, D >

D-ary heap, slightly faster than binary heap due to less random memory access.

A drop-in replacement for std::priority_queue, but is min-heap by default, since min-heap is much more common.

For performance analysis, see https://en.wikipedia.org/wiki/D-ary_heap.

Template Parameters

T	Type of elements.
Comp	Comparison function object. Note that this is a min-heap, as opposed to std::priority_queue, so the element on the top is the smallest element ordered by the comparison function.
D	Number of tree branches. It should be a power of two for fast arithmetics. The default value of 8 is good for general competitive programming use. A larger D leads to faster insertion at the cost of slower deletion.

Member Function Documentation

emplace()

template<typename T , typename Comp = std::less<T>, int D = 8>

template<typename... Args>

void cplib::DaryHeap< T, Comp, D >::emplace ( Args &&...  args )

inline

Construct a new element in place in the heap.

Compare and swap elements \(O(\log_D N)\) times.

pop()

template<typename T , typename Comp = std::less<T>, int D = 8>

void cplib::DaryHeap< T, Comp, D >::pop ( )

inline

Remove the top element from the heap.

The heap must be non-empty before calling this method. Compare elements \(O(D\log_D N)\) times and swap them \(O(\log_D N)\) times.

push() [1/2]

template<typename T , typename Comp = std::less<T>, int D = 8>

void cplib::DaryHeap< T, Comp, D >::push ( const T &  t )

inline

Insert an element into the heap.

Compare and swap elements \(O(\log_D N)\) times.

push() [2/2]

template<typename T , typename Comp = std::less<T>, int D = 8>

void cplib::DaryHeap< T, Comp, D >::push ( T &&  t )

inline

Insert an element into the heap.

Compare and swap elements \(O(\log_D N)\) times.

---

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

• src/cplib/order/dary_heap.hpp