Movatterモバイル変換

[0]ホーム
URL:

cppreference.com
Namespaces
Variants
    Actions

      std::make_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
      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 make_heap( RandomIt first, RandomIt last);
      		 (1)(constexpr since C++20)
      template<class RandomIt,class Compare>
      void make_heap( RandomIt first, RandomIt last, Compare comp);
      		 (2)(constexpr since C++20)

      Constructs aheap in the range[first, last).

      1) The constructed heap is with respect tooperator<(until C++20)std::less{}(since C++20).
      2) The constructed heap is with respect tocomp.

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

      (until C++11)
      (since C++11)

      Contents

      [edit]Parameters

      first, last - the pair of iterators defining therange of elements to make the binary heap 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 3N\)3N comparisons usingoperator<(until C++20)std::less{}(since C++20).
      2) At most\(\scriptsize 3N\)3N applications of the comparison functioncomp.

      [edit]Example

      Run this code
      #include <algorithm>#include <functional>#include <iostream>#include <string_view>#include <vector> void print(std::string_view text,conststd::vector<int>& v={}){std::cout<< text<<": ";for(constauto& e: v)std::cout<< e<<' ';std::cout<<'\n';} int main(){    print("Max heap"); std::vector<int> v{3,2,4,1,5,9};    print("initially, v", v);     std::make_heap(v.begin(), v.end());    print("after make_heap, v", v); std::pop_heap(v.begin(), v.end());    print("after pop_heap, v", v); auto top= v.back();    v.pop_back();    print("former top element",{top});    print("after removing the former top element, v", v);     print("\nMin heap"); std::vector<int> v1{3,2,4,1,5,9};    print("initially, v1", v1);     std::make_heap(v1.begin(), v1.end(),std::greater<>{});    print("after make_heap, v1", v1); std::pop_heap(v1.begin(), v1.end(),std::greater<>{});    print("after pop_heap, v1", v1); auto top1= v1.back();    v1.pop_back();    print("former top element",{top1});    print("after removing the former top element, v1", v1);}

      Output:

      Max heap:initially, v: 3 2 4 1 5 9after make_heap, v: 9 5 4 1 2 3after pop_heap, v: 5 3 4 1 2 9former top element: 9after removing the former top element, v: 5 3 4 1 2 Min heap:initially, v1: 3 2 4 1 5 9after make_heap, v1: 1 2 4 3 5 9after pop_heap, v1: 2 3 4 9 5 1former top element: 1after removing the former top element, v1: 2 3 4 9 5

      [edit]Defect reports

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

      DRApplied toBehavior as publishedCorrect behavior
      LWG 3032C++98the elements of[first, last) was not required to be swappablerequired

      [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]
      adds an element to a max heap
      (function template)[edit]
      removes the largest element from a max heap
      (function template)[edit]
      turns a max heap into a range of elements sorted in ascending order
      (function template)[edit]
      adapts a container to provide priority queue
      (class template)[edit]
      creates a max heap out of a range of elements
      (algorithm function object)[edit]
      Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/make_heap&oldid=180602"
      [8]ページ先頭
      ©2009-2025 Movatter.jp