23 Algorithms library [algorithms]

23.7 Sorting and related operations [alg.sorting]

23.7.7 Heap operations [alg.heap.operations]

1
#
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, , comp(a[], a[i]) is false.
  • (1.2)
    *a may be removed by pop_­heap(), or a new element added by push_­heap(), in time.
2
#
These properties make heaps useful as priority queues.
3
#
make_­heap() converts a range into a heap and sort_­heap() turns a heap into a sorted sequence.

23.7.7.1 push_­heap [push.heap]

🔗
template<class RandomAccessIterator> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
#
Requires: The range [first, last - 1) shall be a valid heap.
The type of *first shall satisfy the Cpp17MoveConstructible requirements (Table 25) and the Cpp17MoveAssignable requirements (Table 27).
2
#
Effects: Places the value in the location last - 1 into the resulting heap [first, last).
3
#
Complexity: At most comparisons.

23.7.7.2 pop_­heap [pop.heap]

🔗
template<class RandomAccessIterator> constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
#
Requires: The range [first, last) shall be a valid non-empty heap.
RandomAccessIterator shall satisfy the Cpp17ValueSwappable requirements ([swappable.requirements]).
The type of *first shall satisfy the Cpp17MoveConstructible (Table 25) and Cpp17MoveAssignable (Table 27) requirements.
2
#
Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap.
3
#
Complexity: At most comparisons.

23.7.7.3 make_­heap [make.heap]

🔗
template<class RandomAccessIterator> constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
#
Requires: The type of *first shall satisfy the Cpp17MoveConstructible requirements (Table 25) and the Cpp17MoveAssignable requirements (Table 27).
2
#
Effects: Constructs a heap out of the range [first, last).
3
#
Complexity: At most comparisons.

23.7.7.4 sort_­heap [sort.heap]

🔗
template<class RandomAccessIterator> constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
1
#
Requires: The range [first, last) shall be a valid heap.
RandomAccessIterator shall satisfy the Cpp17ValueSwappable requirements ([swappable.requirements]).
The type of *first shall satisfy the Cpp17MoveConstructible (Table 25) and Cpp17MoveAssignable (Table 27) requirements.
2
#
Effects: Sorts elements in the heap [first, last).
3
#
Complexity: At most comparisons, where .

23.7.7.5 is_­heap [is.heap]

🔗
template<class RandomAccessIterator> constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last);
1
#
Returns: is_­heap_­until(first, last) == last.
🔗
template<class ExecutionPolicy, class RandomAccessIterator> bool is_heap(ExecutionPolicy&& exec, RandomAccessIterator first, RandomAccessIterator last);
2
#
Returns: is_­heap_­until(std​::​forward<ExecutionPolicy>(exec), first, last) == last.
🔗
template<class RandomAccessIterator, class Compare> constexpr bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
3
#
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);
4
#
Returns: 
is_heap_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
🔗
template<class RandomAccessIterator> constexpr 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> constexpr 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);
5
#
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.
6
#
Complexity: Linear.