This class implements an addressable integer priority queue, precisely a d-ary heap. More...

#include <d_ary_addressable_int_heap.hpp>

Public Types
using	key_type = KeyType

using	compare_type = Compare

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

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

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

DAryAddressableIntHeap &	operator= (const DAryAddressableIntHeap &)=default

	DAryAddressableIntHeap (DAryAddressableIntHeap &&)=default
	Move. More...

DAryAddressableIntHeap &	operator= (DAryAddressableIntHeap &&)=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...

void	remove (key_type key)
	Removes the item with key `key`. 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...

void	update (key_type key)
	Updates the priority queue after the priority associated to the item with key `key` has been changed; if the key `key` is not present in the priority queue, it will be added. More...

bool	contains (key_type key) const
	Returns true if the key `key` is in the heap, false otherwise. 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

Static Protected Member Functions
static constexpr key_type	not_present ()
	Marks a key that is not in the heap. More...

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

std::vector< key_type >	handles_
	Positions of the keys in the heap vector. 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, class Compare = std::less<KeyType>>
class tlx::DAryAddressableIntHeap< KeyType, Arity, Compare >

This class implements an addressable integer priority queue, precisely a d-ary heap.

Keys must be unique unsigned integers. The addressable heap holds an array indexed by the keys, hence it requires a multiple of the highest integer key as space!

Template Parameters

KeyType	Has to be an unsigned integer type.
Arity	A positive integer.
Compare	Function object.

Definition at line 41 of file d_ary_addressable_int_heap.hpp.

Member Typedef Documentation

using compare_type = Compare

Definition at line 50 of file d_ary_addressable_int_heap.hpp.

using key_type = KeyType

Definition at line 49 of file d_ary_addressable_int_heap.hpp.

Constructor & Destructor Documentation

DAryAddressableIntHeap ( compare_type cmp = compare_type() )

inlineexplicit

Allocates an empty heap.

Definition at line 71 of file d_ary_addressable_int_heap.hpp.

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

default

Copy.

DAryAddressableIntHeap ( DAryAddressableIntHeap< 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 207 of file d_ary_addressable_int_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 213 of file d_ary_addressable_int_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 220 of file d_ary_addressable_int_heap.hpp.

size_t capacity ( ) const

inlinenoexcept

Returns the capacity of the heap.

Definition at line 100 of file d_ary_addressable_int_heap.hpp.

void clear ( )

inline

Empties the heap.

Definition at line 91 of file d_ary_addressable_int_heap.hpp.

bool contains ( key_type key ) const

inline

Returns true if the key key is in the heap, false otherwise.

Definition at line 201 of file d_ary_addressable_int_heap.hpp.

bool empty ( ) const

inlinenoexcept

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

Definition at line 103 of file d_ary_addressable_int_heap.hpp.

key_type extract_top ( )

inline

Removes and returns the top item.

Definition at line 168 of file d_ary_addressable_int_heap.hpp.

void heapify ( )

inlineprivate

Reorganize heap_ into a heap.

Definition at line 319 of file d_ary_addressable_int_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 266 of file d_ary_addressable_int_heap.hpp.

static constexpr key_type not_present ( )

inlinestaticprotected

Marks a key that is not in the heap.

Definition at line 65 of file d_ary_addressable_int_heap.hpp.

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

default

DAryAddressableIntHeap& operator= ( DAryAddressableIntHeap< 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 269 of file d_ary_addressable_int_heap.hpp.

void pop ( )

inline

Removes the top item.

Definition at line 165 of file d_ary_addressable_int_heap.hpp.

void push ( const key_type & new_key )

inline

Inserts a new item.

Definition at line 106 of file d_ary_addressable_int_heap.hpp.

void push ( key_type && new_key )

inline

Inserts a new item.

Definition at line 123 of file d_ary_addressable_int_heap.hpp.

void remove ( key_type key )

inline

Removes the item with key key.

Definition at line 140 of file d_ary_addressable_int_heap.hpp.

void reserve ( size_t new_size )

inline

Allocates space for new_size items.

Definition at line 75 of file d_ary_addressable_int_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 229 of file d_ary_addressable_int_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 287 of file d_ary_addressable_int_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 273 of file d_ary_addressable_int_heap.hpp.

size_t size ( ) const

inlinenoexcept

Returns the number of items in the heap.

Definition at line 97 of file d_ary_addressable_int_heap.hpp.

const key_type& top ( ) const

inlinenoexcept

Returns the top item.

Definition at line 159 of file d_ary_addressable_int_heap.hpp.

void update ( key_type key )

inline

Updates the priority queue after the priority associated to the item with key key has been changed; if the key key is not present in the priority queue, it will be added.

Note: if not called after a priority is changed, the behavior of the data structure is undefined.

Definition at line 187 of file d_ary_addressable_int_heap.hpp.

void update_all ( )

inline

Rebuilds the heap.

Definition at line 175 of file d_ary_addressable_int_heap.hpp.