# 11 Algorithms library [algorithms]

## 11.5 Sorting and related operations [alg.sorting]

### 11.5.6 Heap operations [alg.heap.operations]

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.

#### 11.5.6.1push_heap[push.heap]

``` 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.

#### 11.5.6.2pop_heap[pop.heap]

``` 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.

#### 11.5.6.3make_heap[make.heap]

``` 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.

#### 11.5.6.4sort_heap[sort.heap]

``` 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.

#### 11.5.6.5is_heap[is.heap]

``` 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.