A heap is a particular organization of elements in a range between two random access iterators [a,b). Its two key properties are:
There is no element greater than *a in the range and
*a may be removed by pop_heap(), or a new element added by push_heap(), in Ο(log(N)) time.
These properties make heaps useful as priority queues.
make_heap() converts a range into a heap and sort_heap() turns a heap into a sorted sequence.
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I push_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
push_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Places the value in the location last - 1 into the resulting heap [first,last).
Requires: The range [first,last - 1) shall be a valid heap.
Returns: last
Complexity: At most log(last - first) applications of the comparison function and projection.
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I pop_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
pop_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Requires: The range [first,last) shall be a valid non-empty heap.
Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first,last - 1) into a heap.
Returns: last
Complexity: At most 2 * log(last - first) applications of the comparison function and projection.
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I make_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
make_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Constructs a heap out of the range [first,last).
Returns: last
Complexity: At most 3 * (last - first) applications of the comparison function and projection.
template <RandomAccessIterator I, Sentinel<I> S, class Comp = less<>,
class Proj = identity>
requires Sortable<I, Comp, Proj>
I sort_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Comp = less<>, class Proj = identity>
requires Sortable<iterator_t<Rng>, Comp, Proj>
safe_iterator_t<Rng>
sort_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Effects: Sorts elements in the heap [first,last).
Requires: The range [first,last) shall be a valid heap.
Returns: last
Complexity: At most N log(N) comparisons (where N == last - first), and exactly twice as many applications of the projection.
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
bool is_heap(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
bool
is_heap(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: is_heap_until(first, last, comp, proj) == last
template <RandomAccessIterator I, Sentinel<I> S, class Proj = identity,
IndirectStrictWeakOrder<projected<I, Proj>> Comp = less<>>
I is_heap_until(I first, S last, Comp comp = Comp{}, Proj proj = Proj{});
template <RandomAccessRange Rng, class Proj = identity,
IndirectStrictWeakOrder<projected<iterator_t<Rng>, Proj>> Comp = less<>>
safe_iterator_t<Rng>
is_heap_until(Rng&& rng, Comp comp = Comp{}, Proj proj = Proj{});
Returns: If distance(first, last) < 2, returns last. Otherwise, returns the last iterator i in [first,last] for which the range [first,i) is a heap.
Complexity: Linear.