tpl_dynArrayHeap.H File Reference

Array-based dynamic binary heap. More...

#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <utility>
#include <tpl_dynArray.H>
#include <ah-errors.H>

Include dependency graph for tpl_dynArrayHeap.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::DynArrayHeap< T, Compare >
	Dynamic heap (priority queue) backed by DynArray. More...
struct	Aleph::DynArrayHeap< T, Compare >::Iterator

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<typename T , class Compare >
size_t	Aleph::sift_up (DynArray< T > &a, const size_t l, const size_t r, Compare &cmp) noexcept
	Restore heap order by moving an element up.
template<typename T , class Compare >
void	Aleph::sift_down (DynArray< T > &a, const size_t l, const size_t r, Compare &cmp) noexcept
	Restore heap order by moving an element down.

Detailed Description

Array-based dynamic binary heap.

Binary heap using DynArray for automatic growth. Efficient for priority queues with unknown size.

Features

• O(log n) insert, extract-min
• Automatic resizing
• Cache-friendly array storage

See also

tpl_binHeap.H Fixed-size array heap

tpl_dynBinHeap.H Node-based heap

Author

Leandro Rabindranath León

Definition in file tpl_dynArrayHeap.H.