Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::sort_heap

      From cppreference.com
      <cpp‎ |algorithm
       
       
      Algorithm library
      Constrained algorithms and algorithms on ranges(C++20)
      Constrained algorithms, e.g.ranges::copy,ranges::sort, ...
      Execution policies(C++17)
      Sorting and related operations
      Partitioning operations
      Sorting operations
      Binary search operations
      (on partitioned ranges)
      Set operations (on sorted ranges)
      Merge operations (on sorted ranges)
      Heap operations
      sort_heap
      (C++11)
      Minimum/maximum operations
      (C++11)
      (C++17)
      Lexicographical comparison operations
      Permutation operations
      C library
      Numeric operations
      Operations on uninitialized memory
       
      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.
      (until C++11)
      (since C++11)

      Contents

      [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 andType2 regardless ofvalue category (thus,Type1& is not allowed, nor isType1 unless forType1 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.

      DRApplied toBehavior as publishedCorrect behavior
      LWG 2444C++98at most\(\scriptsize N \cdot \log(N)\)N⋅log(N) comparisons were allowedincreased to\(\scriptsize 2N \cdot \log(N)\)2N⋅log(N)

      [edit]See also

      (C++11)
      		 checks if the given range is a max heap
      (function template)[edit]
      finds the largest subrange that is a max heap
      (function template)[edit]
      creates a max heap out of a range of elements
      (function template)[edit]
      removes the largest element from a max heap
      (function template)[edit]
      adds an element to a max heap
      (function template)[edit]
      turns a max heap into a range of elements sorted in ascending order
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/sort_heap&oldid=180605"
      [8]ページ先頭
      ©2009-2025 Movatter.jp