std::sort_heap

From cppreference.com

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros(C++20)
Language support library
Concepts library(C++20)
Diagnostics library
Memory management library
Metaprogramming library(C++11)
General utilities library
Containers library
Iterators library
Ranges library(C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library(C++17)
Concurrency support library(C++11)
Execution control library(C++26)
Technical specifications
Symbols index
External libraries

[edit]

Algorithm library

Constrained algorithms and algorithms on ranges(C++20)

Constrained algorithms, e.g.ranges::copy,ranges::sort, ...

Execution policies(C++17)

is_execution_policy

(C++17)

execution::seqexecution::parexecution::par_unseqexecution::unseq

(C++17) (C++17)(C++17)(C++20)

execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced

(C++17)(C++17)(C++17)(C++20)

Non-modifying sequence operations

(C++17)

all_ofany_ofnone_of (C++11) (C++11)(C++11)
countcount_if
mismatch
equal

findfind_iffind_if_not (C++11)
find_end
find_first_of
adjacent_find
search
search_n

Modifying sequence operations

Copy operations

copycopy_if (C++11)
copy_backward

copy_n (C++11)
move (C++11)
move_backward (C++11)

Swap operations

swap
iter_swap

swap_ranges

Transformation operations

replacereplace_if
transform

replace_copyreplace_copy_if

Generation operations

fill
fill_n

generate
generate_n

Removing operations

removeremove_if
unique

remove_copyremove_copy_if
unique_copy

Order-changing operations

reverse
reverse_copy
rotate
rotate_copy

random_shuffleshuffle (until C++17)(C++11)
shift_leftshift_right (C++20)(C++20)

Sampling operations

sample

(C++17)

Sorting and related operations

Partitioning operations

partition
partition_copy (C++11)
stable_partition

is_partitioned (C++11)
partition_point (C++11)

Sorting operations

sort
stable_sort
partial_sort
partial_sort_copy

is_sorted (C++11)
is_sorted_until (C++11)
nth_element

Binary search operations
(on partitioned ranges)

lower_bound
upper_bound

equal_range
binary_search

Set operations (on sorted ranges)

includes
set_union
set_intersection

set_difference
set_symmetric_difference

Merge operations (on sorted ranges)

merge

inplace_merge

Heap operations

push_heap
pop_heap
make_heap

sort_heap
is_heap (C++11)
is_heap_until (C++11)

Minimum/maximum operations

max
min
minmax (C++11)
clamp (C++17)

max_element
min_element
minmax_element (C++11)

Lexicographical comparison operations

lexicographical_compare

lexicographical_compare_three_way

(C++20)

Permutation operations

next_permutation
prev_permutation

is_permutation (C++11)

iota (C++11)
inner_product
adjacent_difference

accumulate
reduce (C++17)
transform_reduce (C++17)

partial_sum
inclusive_scan (C++17)
exclusive_scan (C++17)

transform_inclusive_scan (C++17)
transform_exclusive_scan (C++17)

Operations on uninitialized memory

uninitialized_copy
uninitialized_move (C++17)
uninitialized_fill

uninitialized_copy_n (C++11)
uninitialized_move_n (C++17)
uninitialized_fill_n

destroy (C++17)
destroy_n (C++17)
destroy_at (C++17)
construct_at (C++20)

uninitialized_default_construct (C++17)
uninitialized_value_construct (C++17)
uninitialized_default_construct_n (C++17)
uninitialized_value_construct_n (C++17)

[edit]

Defined in header`<algorithm>`
template<class RandomIt> void sort_heap( RandomIt first, RandomIt last);	(1)	(constexpr since C++20)
template<class RandomIt,class Compare> void sort_heap( RandomIt first, RandomIt last, Compare comp);	(2)	(constexpr since C++20)

Converts theheap[first, last) into a sorted range. The heap property is no longer maintained.

1) The heap is with respect tooperator<(until C++20)std::less{}(since C++20), and will be sorted with respect tooperator<(until C++20)std::less{}(since C++20).

2) The heap is with respect tocomp, and will be sorted with respect tocomp.

If any of the following conditions is satisfied, the behavior is undefined:

[first, last) is not a heap.

The type of*first is notSwappable.	(until C++11)
`RandomIt` is notValueSwappable. The type offirst is notMoveConstructible. The type offirst is notMoveAssignable.	(since C++11)

[edit]Parameters

first, last	-	the pair of iterators defining the binary heaprange of elements to make the sorted range
comp	-	comparison function object (i.e. an object that satisfies the requirements ofCompare) which returnstrue if the first argument isless than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1& a,const Type2& b); While the signature does not need to haveconst&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const)`Type1` and`Type2` regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless for`Type1` a move is equivalent to a copy(since C++11)). The typesType1 andType2 must be such that an object of typeRandomIt can be dereferenced and then implicitly converted to both of them.
Type requirements
- `RandomIt` must meet the requirements ofLegacyRandomAccessIterator.
- `Compare` must meet the requirements ofCompare.

[edit]Complexity

Given\(\scriptsize N\)N asstd::distance(first, last):

1) At most\(\scriptsize 2N \cdot \log(N)\)2N⋅log(N) comparisons usingoperator<(until C++20)std::less{}(since C++20).

2) At most\(\scriptsize 2N \cdot \log(N)\)2N⋅log(N) applications of the comparison functioncomp.

[edit]Possible implementation

sort_heap (1)

template<class RandomIt>void sort_heap(RandomIt first, RandomIt last){while(first!= last)std::pop_heap(first, last--);}

sort_heap (2)

template<class RandomIt,class Compare>void sort_heap(RandomIt first, RandomIt last, Compare comp){while(first!= last)std::pop_heap(first, last--, comp);}

[edit]Example

Run this code

#include <algorithm>#include <iostream>#include <string_view>#include <vector> void println(std::string_view fmt,constauto& v){for(std::cout<< fmt;constauto&i: v)std::cout<< i<<' ';std::cout<<'\n';} int main(){std::vector<int> v{3,1,4,1,5,9}; std::make_heap(v.begin(), v.end());    println("after make_heap, v: ", v);     std::sort_heap(v.begin(), v.end());    println("after sort_heap, v: ", v);}

Output:

after make_heap, v: 9 4 5 1 1 3after sort_heap, v: 1 1 3 4 5 9

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 2444	C++98	at most\(\scriptsize N \cdot \log(N)\)N⋅log(N) comparisons were allowed	increased to\(\scriptsize 2N \cdot \log(N)\)2N⋅log(N)

[edit]See also

is_heap (C++11)	checks if the given range is a max heap (function template)[edit]
is_heap_until (C++11)	finds the largest subrange that is a max heap (function template)[edit]
make_heap	creates a max heap out of a range of elements (function template)[edit]
pop_heap	removes the largest element from a max heap (function template)[edit]
push_heap	adds an element to a max heap (function template)[edit]
ranges::sort_heap (C++20)	turns a max heap into a range of elements sorted in ascending order (algorithm function object)[edit]