Difference between revisions of "cpp/algorithm/ranges/sort heap"

Latest revision as of 01:41, 15 October 2024

Defined in header `<algorithm>`
Call signature
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );	(1)	(since C++20)
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> sort_heap( R&& r, Comp comp = {}, Proj proj = {} );	(2)	(since C++20)

Sorts the elements in the specified range with respect to comp and proj, where the range originally represents a heap with respect to comp and proj. The sorted range no longer maintains the heap property.

1) The specified range is [first, last).

2) The specified range is r.

If the specified range is not a heap with respect to comp and proj, the behavior is undefined.

The function-like entities described on this page are niebloids, that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions.

struct sort_heap_fn
{
    template<std::random_access_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
        requires std::sortable<I, Comp, Proj>
    constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        auto ret{ranges::next(first, last)};
        for (; first != last; --last)
            ranges::pop_heap(first, last, comp, proj);
        return ret;
    }
 
    template<ranges::random_access_range R,
             class Comp = ranges::less, class Proj = std::identity>
        requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj));
    }
};
 
inline constexpr sort_heap_fn sort_heap{};

[edit] Example

Run this code

#include <algorithm>
#include <array>
#include <iostream>
 
void print(auto const& rem, const auto& v)
{
    std::cout << rem;
    for (const auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::array v{3, 1, 4, 1, 5, 9};
    print("original array:  ", v);
 
    std::ranges::make_heap(v);
    print("after make_heap: ", v);
 
    std::ranges::sort_heap(v);
    print("after sort_heap: ", v);
}

Output:

original array:  3 1 4 1 5 9
after make_heap: 9 5 4 1 1 3
after sort_heap: 1 1 3 4 5 9

[edit] See also

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

@@ Line 7: / Line 7: @@
 template< std::random_access_iterator I, std::sentinel_for<I> S,
            class Comp = ranges::less, class Proj = std::identity >
-requires std::sortable<I, Comp, Proj>
+    requires std::sortable<I, Comp, Proj>
-constexpr I
+constexpr I sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );
-    sort_heap( I first, S last, Comp comp = {}, Proj proj = {} );
 }}
 {{dcl|num=2|since=c++20|1=
-template< ranges::random_access_range R, class Comp = ranges::less,
+template< ranges::random_access_range R,
-          class Proj = std::identity >
+          class Comp = ranges::less, class Proj = std::identity >
-requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
+    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
 constexpr ranges::borrowed_iterator_t<R>
      sort_heap( R&& r, Comp comp = {}, Proj proj = {} );
@@ Line 20: / Line 19: @@
 {{dcl end}}
-Converts the [[enwiki:Binary_heap|''max heap'']] {{range|first|last}} into a sorted range in ascending order. The resulting range no longer has the heap property.
+[[cpp/algorithm#Requirements|Sorts]] the elements in the specified range with respect to {{c|comp}} and {{c|proj}}, where the range originally represents a [[cpp/algorithm#Heap operations|heap]] with respect to {{c|comp}} and {{c|proj}}. The sorted range no longer maintains the heap property.
-@1@ Elements are compared using the given binary comparison function {{c|comp}} and projection object {{c|proj}}.
+@1@ The specified range is {{range|first|last}}.
-@2@ Same as {{v|1}}, but uses {{c|r}} as the range, as if using {{c|ranges::begin(r)}} as {{c|first}} and {{c|ranges::end(r)}} as {{c|last}}.
+@2@ The specified range is {{c|r}}.
+If the specified range is not a heap with respect to {{c|comp}} and {{c|proj}}, the behavior is undefined.
 {{cpp/ranges/niebloid}}
@@ Line 30: / Line 31: @@
 ===Parameters===
 {{par begin}}
-{{par|first, last|the range of elements to sort}}
+{{par|first, last|the iterator and sentinel designating the range of elements to modify}}
-{{par|r|the range of elements to sort}}
+{{par|r|the range of elements to modify}}
-{{par|pred|predicate to apply to the projected elements}}
+{{par|comp|comparator to apply to the projected elements}}
 {{par|proj|projection to apply to the elements}}
 {{par end}}
 ===Return value===
-An iterator equal to {{c|last}}.
+@1@ {{c|last}}
+@2@ {{c|ranges::end(r)}}
 ===Complexity===
-Given {{c|1= N = ranges::distance(first, last)}}, at most {{mathjax-or|\(\scriptsize 2N\log{(N)}\)|2Nlog(N)}} comparisons and {{mathjax-or|\(\scriptsize 4N\log{(N)}\)|4Nlog(N)}} projections.
+At most {{mathjax-or|\(\scriptsize 2N \cdot \log(N)\)|2N⋅log(N)}} applications of {{c|comp}} and {{mathjax-or|\(\scriptsize 4N \cdot \log(N)\)|4N⋅log(N)}} applications of {{c|proj}}, where {{mathjax-or|\(\scriptsize N \)|N}} is:
+@1@ {{c|ranges::distance(first, last)}}
-===Notes===
+@2@ {{c|ranges::distance(r)}}
-{{cpp/algorithm/ranges/notes heap}}
 ===Possible implementation===
@@ Line 51: / Line 52: @@
      template<std::random_access_iterator I, std::sentinel_for<I> S,
               class Comp = ranges::less, class Proj = std::identity>
-    requires std::sortable<I, Comp, Proj>
+        requires std::sortable<I, Comp, Proj>
-     constexpr I
+     constexpr I operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
-        operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
      {
-         auto ret {ranges::next(first, last)};
+         auto ret{ranges::next(first, last)};
          for (; first != last; --last)
              ranges::pop_heap(first, last, comp, proj);
@@ Line 61: / Line 61: @@
      }
-     template<ranges::random_access_range R, class Comp = ranges::less,
+     template<ranges::random_access_range R,
-             class Proj = std::identity>
+             class Comp = ranges::less, class Proj = std::identity>
-    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
+        requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
      constexpr ranges::borrowed_iterator_t<R>
          operator()(R&& r, Comp comp = {}, Proj proj = {}) const
@@ Line 71: / Line 71: @@
 };
-inline constexpr sort_heap_fn sort_heap {};
+inline constexpr sort_heap_fn sort_heap{};
 }}
@@ Line 80: / Line 80: @@
 #include <iostream>
-void print(auto const& rem, auto const& v)
+void print(auto const& rem, const auto& v)
 {
      std::cout << rem;
@@ Line 90: / Line 90: @@
 int main()
 {
-     std::array v {3, 1, 4, 1, 5, 9};
+     std::array v{3, 1, 4, 1, 5, 9};
      print("original array:  ", v);
      std::ranges::make_heap(v);
      print("after make_heap: ", v);
      std::ranges::sort_heap(v);
      print("after sort_heap: ", v);

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)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

first, last	-	the iterator and sentinel designating the range of elements to modify
r	-	the range of elements to modify
comp	-	comparator to apply to the projected elements
proj	-	projection to apply to the elements

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/ranges/sort heap"

Latest revision as of 01:41, 15 October 2024

Contents

[edit] Parameters

[edit] Return value

[edit] Complexity

[edit] Possible implementation

[edit] Example

[edit] See also

Navigation

Toolbox