Defined in header `<algorithm>` | ||
---|---|---|

(1) | ||

template< class RandomIt > void sort_heap( RandomIt first, RandomIt last ); | (until C++20) | |

template< class RandomIt > constexpr void sort_heap( RandomIt first, RandomIt last ); | (since C++20) | |

(2) | ||

template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp ); | (until C++20) | |

template< class RandomIt, class Compare > constexpr void sort_heap( RandomIt first, RandomIt last, Compare comp ); | (since C++20) |

Converts the *max heap* `[first, last)`

into a sorted range in ascending order. The resulting range no longer has the heap property.

The first version of the function uses `operator<`

to compare the elements, the second uses the given comparison function `comp`

.

first, last | - | the range of elements to sort |

comp | - | comparison function object (i.e. an object that satisfies the requirements of Compare) which returns `true` if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
While the signature does not need to have |

Type requirements | ||

-`RandomIt` must meet the requirements of ValueSwappable and LegacyRandomAccessIterator. |
||

-The type of dereferenced `RandomIt` must meet the requirements of MoveAssignable and MoveConstructible. |

(none).

At most *2×N×log(N)* comparisons where `N=std::distance(first, last)`

.

A *max heap* is a range of elements `[f,l)`

that has the following properties:

- With
`N = l - f`

, for all`0 < i < N`

,`f[floor(`

does not compare less thani-1 2 `f[i]`

. - a new element can be added using
`std::push_heap()`

- the first element can be removed using
`std::pop_heap()`

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 | complexity requirement was wrong by a factor of 2 | corrected |

First version |
---|

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

Second version |

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

#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> v = {3, 1, 4, 1, 5, 9}; std::make_heap(v.begin(), v.end()); std::cout << "heap:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::sort_heap(v.begin(), v.end()); std::cout << "\nsorted:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::cout << '\n'; }

Output:

heap: 9 4 5 1 1 3 sorted: 1 1 3 4 5 9

creates a max heap out of a range of elements (function template) |

© cppreference.com

Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.

http://en.cppreference.com/w/cpp/algorithm/sort_heap