tlx
Loading...
Searching...
No Matches
DAryAddressableIntHeap< KeyType, Arity, Compare > Class Template Reference

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
 
using compare_type
 

Public Member Functions

 DAryAddressableIntHeap (compare_type cmp=compare_type())
 Allocates an empty heap.
 
void reserve (size_t new_size)
 Allocates space for new_size items.
 
 DAryAddressableIntHeap (const DAryAddressableIntHeap &)=default
 Copy.
 
DAryAddressableIntHeapoperator= (const DAryAddressableIntHeap &)=default
 
 DAryAddressableIntHeap (DAryAddressableIntHeap &&)=default
 Move.
 
DAryAddressableIntHeapoperator= (DAryAddressableIntHeap &&)=default
 
void clear ()
 Empties the heap.
 
size_t size () const noexcept
 Returns the number of items in the heap.
 
size_t capacity () const noexcept
 Returns the capacity of the heap.
 
bool empty () const noexcept
 Returns true if the heap has no items, false otherwise.
 
void push (const key_type &new_key)
 Inserts a new item.
 
void push (key_type &&new_key)
 Inserts a new item.
 
void remove (key_type key)
 Removes the item with key key.
 
const key_typetop () const noexcept
 Returns the top item.
 
void pop ()
 Removes the top item.
 
key_type extract_top ()
 Removes and returns the top item.
 
void update_all ()
 Rebuilds the heap.
 
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.
 
bool contains (key_type key) const
 Returns true if the key key is in the heap, false otherwise.
 
template<class InputIterator >
void build_heap (InputIterator first, InputIterator last)
 Builds a heap from a container.
 
void build_heap (const std::vector< key_type > &keys)
 Builds a heap from the vector keys. Items of keys are copied.
 
void build_heap (std::vector< key_type > &&keys)
 Builds a heap from the vector keys. Items of keys are moved.
 
bool sanity_check ()
 For debugging: runs a BFS from the root node and verifies that the heap property is respected.
 

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.
 

Protected Attributes

std::vector< key_typeheap_
 Cells in the heap.
 
std::vector< key_typehandles_
 Positions of the keys in the heap vector.
 
compare_type cmp_
 Compare function.
 

Private Member Functions

size_t left (size_t k) const
 Returns the position of the left child of the node at position k.
 
size_t parent (size_t k) const
 Returns the position of the parent of the node at position k.
 
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.
 
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.
 
void heapify ()
 Reorganize heap_ into a heap.
 

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
KeyTypeHas to be an unsigned integer type.
ArityA positive integer.
CompareFunction object.

Definition at line 41 of file d_ary_addressable_int_heap.hpp.

Member Typedef Documentation

◆ compare_type

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
using compare_type

Definition at line 50 of file d_ary_addressable_int_heap.hpp.

◆ key_type

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
using key_type

Definition at line 49 of file d_ary_addressable_int_heap.hpp.

Constructor & Destructor Documentation

◆ DAryAddressableIntHeap() [1/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
DAryAddressableIntHeap ( compare_type cmp = compare_type())
inlineexplicit

Allocates an empty heap.

Definition at line 71 of file d_ary_addressable_int_heap.hpp.

◆ DAryAddressableIntHeap() [2/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
DAryAddressableIntHeap ( const DAryAddressableIntHeap< KeyType, Arity, Compare > & )
default

Copy.

◆ DAryAddressableIntHeap() [3/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
DAryAddressableIntHeap ( DAryAddressableIntHeap< KeyType, Arity, Compare > && )
default

Move.

Member Function Documentation

◆ build_heap() [1/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ build_heap() [2/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
template<class InputIterator >
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.

◆ build_heap() [3/3]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ capacity()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
size_t capacity ( ) const
inlinenoexcept

Returns the capacity of the heap.

Definition at line 100 of file d_ary_addressable_int_heap.hpp.

◆ clear()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void clear ( )
inline

Empties the heap.

Definition at line 91 of file d_ary_addressable_int_heap.hpp.

◆ contains()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ empty()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ extract_top()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
key_type extract_top ( )
inline

Removes and returns the top item.

Definition at line 168 of file d_ary_addressable_int_heap.hpp.

◆ heapify()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void heapify ( )
inlineprivate

Reorganize heap_ into a heap.

Definition at line 319 of file d_ary_addressable_int_heap.hpp.

◆ left()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ not_present()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
static constexpr key_type not_present ( )
inlinestaticconstexprprotected

Marks a key that is not in the heap.

Definition at line 65 of file d_ary_addressable_int_heap.hpp.

◆ operator=() [1/2]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
DAryAddressableIntHeap & operator= ( const DAryAddressableIntHeap< KeyType, Arity, Compare > & )
default

◆ operator=() [2/2]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
DAryAddressableIntHeap & operator= ( DAryAddressableIntHeap< KeyType, Arity, Compare > && )
default

◆ parent()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ pop()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void pop ( )
inline

Removes the top item.

Definition at line 165 of file d_ary_addressable_int_heap.hpp.

◆ push() [1/2]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void push ( const key_type & new_key)
inline

Inserts a new item.

Definition at line 106 of file d_ary_addressable_int_heap.hpp.

◆ push() [2/2]

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void push ( key_type && new_key)
inline

Inserts a new item.

Definition at line 123 of file d_ary_addressable_int_heap.hpp.

◆ remove()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void remove ( key_type key)
inline

Removes the item with key key.

Definition at line 140 of file d_ary_addressable_int_heap.hpp.

◆ reserve()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ sanity_check()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ sift_down()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ sift_up()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ top()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
const key_type & top ( ) const
inlinenoexcept

Returns the top item.

Definition at line 159 of file d_ary_addressable_int_heap.hpp.

◆ update()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
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.

◆ update_all()

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
void update_all ( )
inline

Rebuilds the heap.

Definition at line 175 of file d_ary_addressable_int_heap.hpp.

Member Data Documentation

◆ arity

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
size_t arity
staticconstexpr

Definition at line 52 of file d_ary_addressable_int_heap.hpp.

◆ cmp_

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
compare_type cmp_
protected

Compare function.

Definition at line 62 of file d_ary_addressable_int_heap.hpp.

◆ handles_

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
std::vector<key_type> handles_
protected

Positions of the keys in the heap vector.

Definition at line 59 of file d_ary_addressable_int_heap.hpp.

◆ heap_

template<typename KeyType , unsigned Arity = 2, class Compare = std::less<KeyType>>
std::vector<key_type> heap_
protected

Cells in the heap.

Definition at line 56 of file d_ary_addressable_int_heap.hpp.


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