tpl_dynArrayHeap.H File Reference

Array-based dynamic binary heap. More...

#include <ah-concepts.H>
#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

Note

Due to the underlying DynArray directory, segment, and block structuring, not all entries in the heap are contiguous in memory. Only the entries within the same block are contiguous.

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.