• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

    最終更新日時(UTC):
    が更新

    履歴 編集

    function template
    <algorithm>

    std::push_heap

    namespace std {
      template <class RandomAccessIterator>
      void push_heap(RandomAccessIterator first,
                     RandomAccessIterator last);           // (1) C++03
    
      template <class RandomAccessIterator>
      constexpr void push_heap(RandomAccessIterator first,
                               RandomAccessIterator last); // (1) C++20
    
      template <class RandomAccessIterator, class Compare>
      void push_heap(RandomAccessIterator first,
                     RandomAccessIterator last,
                     Compare comp);                        // (2) C++03
    
      template <class RandomAccessIterator, class Compare>
      constexpr void push_heap(RandomAccessIterator first,
                               RandomAccessIterator last,
                               Compare comp);              // (2) C++20
    }
    

    概要

    ヒープ化されたイテレータ範囲[first, last - 1)に要素を追加する。

    この関数は、イテレータ範囲の末尾要素*(last - 1)を、範囲全体がヒープとなるよう配置し直す。

    テンプレートパラメータ制約

    • *first の型は MoveConstructibleMoveAssignable の要件を満たしていること

    事前条件

    • [first,last - 1) は有効なヒープであること

    効果

    last - 1 の値を、[first,last) が有効なヒープとなるように配置する

    戻り値

    なし

    計算量

    最大で log(last - first) 回比較する。

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    int main()
    {
      std::vector<int> v = {3, 1, 4};
    
      std::make_heap(v.begin(), v.end());
    
      // 要素を追加してヒープ化
      v.push_back(2);
      std::push_heap(v.begin(), v.end());
    
      std::sort_heap(v.begin(), v.end());
    
      std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << std::endl;
      });
    }
    

    出力

    1
    2
    3
    4
    

    実装例

    template <class RandomAccessIterator>
    void push_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
      using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type;
      using value_type      = typename std::iterator_traits<RandomAccessIterator>::value_type;
      difference_type c = last - first - 1;
      value_type v = std::move(first[c]);
      while (c > 0) {
        difference_type p = (c - 1) / 2;
        if (!bool(first[p] < v))
          break;
        first[c] = std::move(first[p]);
        c = p;
      }
      first[c] = std::move(v);
    }
    
    template <class RandomAccessIterator, class Compare>
    void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
    {
      using difference_type = typename std::iterator_traits<RandomAccessIterator>::difference_type;
      using value_type      = typename std::iterator_traits<RandomAccessIterator>::value_type;
    
      difference_type c = last - first - 1;
      value_type v = std::move(first[c]);
      while (c > 0) {
        difference_type p = (c - 1) / 2;
        if (!bool(comp(first[p], v)))
          break;
        first[c] = std::move(first[p]);
        c = p;
      }
      first[c] = std::move(v);
    }
    

    参照