tpl_arrayHeap.H File Reference

Fixed-capacity binary heap and heapsort algorithms. More...

#include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <utility>
#include <ahFunction.H>
#include <ahUtils.H>
#include <ahDefs.H>
#include <ahAssert.H>
#include <array_it.H>
#include <htlist.H>
#include <tpl_dynDlist.H>
#include <ah-args-ctor.H>
#include <ahDry.H>
#include <ah-dry.H>
#include <ah-errors.H>

Include dependency graph for tpl_arrayHeap.H:

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

Go to the source code of this file.

Classes
class	Aleph::ArrayHeap< T, Compare >
	Fixed-capacity binary heap backed by a raw array. More...
struct	Aleph::ArrayHeap< T, Compare >::Iterator

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

Functions
template<typename T , class Compare >
T &	Aleph::sift_up (T *ptr, const size_t l, const size_t r, Compare &cmp)
	Restore the heap property by moving the element at position r upwards.
template<typename T , class Compare >
void	Aleph::sift_down (T *ptr, const size_t l, const size_t r, Compare &cmp)
	Restore the heap property by moving the element at position l downwards.
template<typename T , class Compare >
void	Aleph::sift_down_up (T *ptr, const size_t l, const size_t i, const size_t r, Compare &cmp)
	Restore the heap property by sifting down and then sifting up.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::heapsort (T *array, const size_t n, const Compare &cmp=Compare())
	Sort an array using the heapsort algorithm.
template<typename T , class Compare = Aleph::less<T>>
void	Aleph::faster_heapsort (T *array, const size_t n, const Compare &cmp=Compare())
	Optimized version of heapsort.
template<typename T , class Compare = Aleph::less<T>>
bool	Aleph::valid_heap (T *array, const size_t l, const size_t r, const Compare &cmp=Compare())
	Check whether a range satisfies the heap property.

Detailed Description

Fixed-capacity binary heap and heapsort algorithms.

This file provides:

• sift_up and sift_down heap operations
• heapsort and faster_heapsort sorting algorithms
• ArrayHeap<T, Compare> fixed-capacity priority queue

All operations use 1-based indexing internally for simpler parent/child arithmetic.

Author

Leandro Rabindranath León

Definition in file tpl_arrayHeap.H.