heap.h File Reference

C++ STL heap implementation with extensions. More...

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

Go to the source code of this file.

Namespaces
	Heap

Functions
template<class _Compare , class _RandomAccessIterator >
void	Heap::sift_up_ (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp, typename std::iterator_traits< _RandomAccessIterator >::difference_type len)
template<class _RandomAccessIterator , class _Compare >
void	Heap::push (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
template<class _Compare , class _RandomAccessIterator >
void	Heap::sift_down_ (_RandomAccessIterator first, _Compare comp, typename std::iterator_traits< _RandomAccessIterator >::difference_type len, _RandomAccessIterator start)
template<class _Compare , class _RandomAccessIterator >
void	Heap::pop_heap_ (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp, typename std::iterator_traits< _RandomAccessIterator >::difference_type len)
template<class _RandomAccessIterator , class _Compare >
void	Heap::pop (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
template<class _Compare , class _RandomAccessIterator >
void	Heap::replace_heap_ (_RandomAccessIterator first, _Compare comp, typename std::iterator_traits< _RandomAccessIterator >::difference_type len)
template<class _RandomAccessIterator , class _Compare >
void	Heap::replace (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
template<class _Compare , class _RandomAccessIterator >
void	Heap::siftdown_heap_ (_RandomAccessIterator first, _RandomAccessIterator elt, _Compare comp, typename std::iterator_traits< _RandomAccessIterator >::difference_type len)
template<class _RandomAccessIterator , class _Compare >
void	Heap::siftdown (_RandomAccessIterator first, _RandomAccessIterator last, _RandomAccessIterator elt, _Compare comp)
template<class _RandomAccessIterator , class _Compare >
void	Heap::make (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)
template<class _Compare , class _RandomAccessIterator >
void	Heap::sort (_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp)

Detailed Description

C++ STL heap implementation with extensions.

Adapted from libc++'s <algorithm>, with the following additions:

• replace() - pop() followed by push(), but as efficient as just pop() (i.e. at most 2 * log(N) compares rather than at most 3 * log(N))
• siftdown() - sink adjusted entry to restore heap invariant

Complexity:

make() : At most 3*N comparisons pop()/replace()/siftdown() : At most 2*log(N) comparisons push() : At most log(N) comparisons (O(1) average) sort() : At most 2*N*log(N) comparisons

Definition in file heap.h.