tlx
DAryHeap< KeyType, Arity, Compare > Class Template Reference

This class implements a d-ary comparison-based heap usable as a priority queue. More...

#include <d_ary_heap.hpp>

Public Types

using key_type = KeyType
 
using compare_type = Compare
 

Public Member Functions

 DAryHeap (compare_type cmp=compare_type())
 Allocates an empty heap. More...
 
void reserve (size_t new_size)
 Allocates space for new_size items. More...
 
 DAryHeap (const DAryHeap &)=default
 Copy. More...
 
DAryHeapoperator= (const DAryHeap &)=default
 
 DAryHeap (DAryHeap &&)=default
 Move. More...
 
DAryHeapoperator= (DAryHeap &&)=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...
 
const key_typetop () 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...
 
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
 

Protected Attributes

std::vector< key_typeheap_
 Cells in the heap. 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, typename Compare = std::less<KeyType>>
class tlx::DAryHeap< KeyType, Arity, Compare >

This class implements a d-ary comparison-based heap usable as a priority queue.

Higher arity yields better cache efficiency.

Template Parameters
KeyTypeKey type.
ArityA positive integer.
CompareFunction object to order keys.

Definition at line 37 of file d_ary_heap.hpp.

Member Typedef Documentation

using compare_type = Compare

Definition at line 43 of file d_ary_heap.hpp.

using key_type = KeyType

Definition at line 42 of file d_ary_heap.hpp.

Constructor & Destructor Documentation

DAryHeap ( compare_type  cmp = compare_type())
inlineexplicit

Allocates an empty heap.

Definition at line 56 of file d_ary_heap.hpp.

DAryHeap ( const DAryHeap< KeyType, Arity, Compare > &  )
default

Copy.

DAryHeap ( DAryHeap< 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 129 of file d_ary_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 135 of file d_ary_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 142 of file d_ary_heap.hpp.

size_t capacity ( ) const
inlinenoexcept

Returns the capacity of the heap.

Definition at line 81 of file d_ary_heap.hpp.

void clear ( )
inline

Empties the heap.

Definition at line 73 of file d_ary_heap.hpp.

bool empty ( ) const
inlinenoexcept

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

Definition at line 84 of file d_ary_heap.hpp.

key_type extract_top ( )
inline

Removes and returns the top item.

Definition at line 116 of file d_ary_heap.hpp.

void heapify ( )
inlineprivate

Reorganize heap_ into a heap.

Definition at line 224 of file d_ary_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 175 of file d_ary_heap.hpp.

DAryHeap& operator= ( const DAryHeap< KeyType, Arity, Compare > &  )
default
DAryHeap& operator= ( DAryHeap< 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 178 of file d_ary_heap.hpp.

void pop ( )
inline

Removes the top item.

Definition at line 107 of file d_ary_heap.hpp.

void push ( const key_type new_key)
inline

Inserts a new item.

Definition at line 87 of file d_ary_heap.hpp.

void push ( key_type &&  new_key)
inline

Inserts a new item.

Definition at line 94 of file d_ary_heap.hpp.

void reserve ( size_t  new_size)
inline

Allocates space for new_size items.

Definition at line 60 of file d_ary_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 151 of file d_ary_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 194 of file d_ary_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 182 of file d_ary_heap.hpp.

size_t size ( ) const
inlinenoexcept

Returns the number of items in the heap.

Definition at line 78 of file d_ary_heap.hpp.

const key_type& top ( ) const
inlinenoexcept

Returns the top item.

Definition at line 101 of file d_ary_heap.hpp.

void update_all ( )
inline

Rebuilds the heap.

Definition at line 123 of file d_ary_heap.hpp.

Member Data Documentation

constexpr size_t arity
static

Definition at line 45 of file d_ary_heap.hpp.

compare_type cmp_
protected

Compare function.

Definition at line 52 of file d_ary_heap.hpp.

std::vector<key_type> heap_
protected

Cells in the heap.

Definition at line 49 of file d_ary_heap.hpp.


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