tlx
Loading...
Searching...
No Matches
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.
 
void reserve (size_t new_size)
 Allocates space for new_size items.
 
 DAryHeap (const DAryHeap &)=default
 Copy.
 
DAryHeapoperator= (const DAryHeap &)=default
 
 DAryHeap (DAryHeap &&)=default
 Move.
 
DAryHeapoperator= (DAryHeap &&)=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.
 
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.
 
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
 

Protected Attributes

std::vector< key_typeheap_
 Cells in the heap.
 
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, 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

◆ compare_type

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

Definition at line 43 of file d_ary_heap.hpp.

◆ key_type

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

Definition at line 42 of file d_ary_heap.hpp.

Constructor & Destructor Documentation

◆ DAryHeap() [1/3]

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

Allocates an empty heap.

Definition at line 56 of file d_ary_heap.hpp.

◆ DAryHeap() [2/3]

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

Copy.

◆ DAryHeap() [3/3]

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

Move.

Member Function Documentation

◆ build_heap() [1/3]

template<typename KeyType , unsigned Arity = 2, typename 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 135 of file d_ary_heap.hpp.

◆ build_heap() [2/3]

template<typename KeyType , unsigned Arity = 2, typename Compare = std::less<KeyType>>
template<class InputIterator >
void build_heap ( InputIterator  first,
InputIterator  last 
)
inline

Builds a heap from a container.

Definition at line 129 of file d_ary_heap.hpp.

◆ build_heap() [3/3]

template<typename KeyType , unsigned Arity = 2, typename 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 142 of file d_ary_heap.hpp.

◆ capacity()

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

Returns the capacity of the heap.

Definition at line 81 of file d_ary_heap.hpp.

◆ clear()

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

Empties the heap.

Definition at line 73 of file d_ary_heap.hpp.

◆ empty()

template<typename KeyType , unsigned Arity = 2, typename Compare = std::less<KeyType>>
bool empty ( ) const
inlinenoexcept

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

Definition at line 84 of file d_ary_heap.hpp.

◆ extract_top()

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

Removes and returns the top item.

Definition at line 116 of file d_ary_heap.hpp.

◆ heapify()

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

Reorganize heap_ into a heap.

Definition at line 224 of file d_ary_heap.hpp.

◆ left()

template<typename KeyType , unsigned Arity = 2, typename 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 175 of file d_ary_heap.hpp.

◆ operator=() [1/2]

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

◆ operator=() [2/2]

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

◆ parent()

template<typename KeyType , unsigned Arity = 2, typename 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 178 of file d_ary_heap.hpp.

◆ pop()

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

Removes the top item.

Definition at line 107 of file d_ary_heap.hpp.

◆ push() [1/2]

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

Inserts a new item.

Definition at line 87 of file d_ary_heap.hpp.

◆ push() [2/2]

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

Inserts a new item.

Definition at line 94 of file d_ary_heap.hpp.

◆ reserve()

template<typename KeyType , unsigned Arity = 2, typename Compare = std::less<KeyType>>
void reserve ( size_t  new_size)
inline

Allocates space for new_size items.

Definition at line 60 of file d_ary_heap.hpp.

◆ sanity_check()

template<typename KeyType , unsigned Arity = 2, typename 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 151 of file d_ary_heap.hpp.

◆ sift_down()

template<typename KeyType , unsigned Arity = 2, typename 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 194 of file d_ary_heap.hpp.

◆ sift_up()

template<typename KeyType , unsigned Arity = 2, typename 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 182 of file d_ary_heap.hpp.

◆ size()

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

Returns the number of items in the heap.

Definition at line 78 of file d_ary_heap.hpp.

◆ top()

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

Returns the top item.

Definition at line 101 of file d_ary_heap.hpp.

◆ update_all()

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

Rebuilds the heap.

Definition at line 123 of file d_ary_heap.hpp.

Member Data Documentation

◆ arity

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

Definition at line 45 of file d_ary_heap.hpp.

◆ cmp_

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

Compare function.

Definition at line 52 of file d_ary_heap.hpp.

◆ heap_

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