28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.7 Heap operations [alg.heap.operations]

A heap is a particular organization of elements in a range between two random access iterators [a, b) such that:

(1.1)
With N = b - a, for all i, $0 < i < N$ , comp(a[ $⌊ \frac{i - 1}{2} ⌋$ ], a[i]) is false.
(1.2)
*a may be removed by pop_heap(), or a new element added by push_heap(), in $O (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.

28.7.7.1 push_heap [push.heap]

template<class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Requires: The range [first, last - 1) shall be a valid heap. The type of *first shall satisfy the MoveConstructible requirements and the MoveAssignable requirements.

Effects: Places the value in the location last - 1 into the resulting heap [first, last).

Complexity: At most $log (last - first)$ comparisons.

28.7.7.2 pop_heap [pop.heap]

template<class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Requires: The range [first, last) shall be a valid non-empty heap. RandomAccessIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.

Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap.

Complexity: At most $2 log (last - first)$ comparisons.

28.7.7.3 make_heap [make.heap]

template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Requires: The type of *first shall satisfy the MoveConstructible requirements and the MoveAssignable requirements.

Effects: Constructs a heap out of the range [first, last).

Complexity: At most $3 (last - first)$ comparisons.

28.7.7.4 sort_heap [sort.heap]

template<class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Requires: The range [first, last) shall be a valid heap. RandomAccessIterator shall satisfy the requirements of ValueSwappable. The type of *first shall satisfy the requirements of MoveConstructible and of MoveAssignable.

Effects: Sorts elements in the heap [first, last).

Complexity: At most $N log N$ comparisons, where $N = last - first$ .

28.7.7.5 is_heap [is.heap]

template<class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

Returns: is_heap_until(first, last) == last

template<class ExecutionPolicy, class RandomAccessIterator> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last);

Returns: is_heap_until(std::forward<ExecutionPolicy>(exec), first, last) == last

template<class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Returns: is_heap_until(first, last, comp) == last

template<class ExecutionPolicy, class RandomAccessIterator, class Compare> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Returns:

is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last

template<class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last); template<class ExecutionPolicy, class RandomAccessIterator> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<class ExecutionPolicy, class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Returns: If (last - first) < 2, returns last. Otherwise, returns the last iterator i in [first, last] for which the range [first, i) is a heap.

Complexity: Linear.

28 Algorithms library [algorithms]

28.7 Sorting and related operations [alg.sorting]

28.7.7 Heap operations [alg.heap.operations]

28.7.7.1 push_­heap [push.heap]

28.7.7.2 pop_­heap [pop.heap]

28.7.7.3 make_­heap [make.heap]

28.7.7.4 sort_­heap [sort.heap]

28.7.7.5 is_­heap [is.heap]

28.7.7.1 push_heap [push.heap]

28.7.7.2 pop_heap [pop.heap]

28.7.7.3 make_heap [make.heap]

28.7.7.4 sort_heap [sort.heap]

28.7.7.5 is_heap [is.heap]