• Class / Function / Type

      std::
    • Header file

      <>
    • Other / All

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

    履歴 編集

    function template
    <algorithm>

    std::pop_heap

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

    概要

    ヒープ化されたイテレータ範囲[first, last)の先頭と末尾を入れ替え、ヒープ範囲を作り直す

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

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

    事前条件

    • [first,last) は空でないヒープであること

    効果

    first にある値を last - 1 と交換し、その後 [first,last - 1) が有効な heap となるように配置する。

    戻り値

    なし

    計算量

    最大で 2 * 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());
    
      // 最後尾要素を削除してヒープ化
      std::pop_heap(v.begin(), v.end());
      v.pop_back();
    
      std::sort_heap(v.begin(), v.end());
    
      std::for_each(v.begin(), v.end(), [](int x) {
        std::cout << x << std::endl;
      });
    }
    

    出力

    1
    3
    

    実装例

    template <class RandomAccessIterator>
    void pop_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;
      --last;
      difference_type len = last - first;
      if (len > 0) {
        value_type v = std::move(*last);
        *last = std::move(*first);
        difference_type p = 0;
        for (difference_type c = 1; c < len; c = p * 2 + 1) {
          if (c + 1 < len && first[c] < first[c + 1])
            ++c;
          if (!bool(v < first[c]))
            break;
          first[p] = std::move(first[c]);
          p = c;
        }
        first[p] = std::move(v);
      }
    }
    
    template <class RandomAccessIterator, class Compare>
    void pop_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;
      --last;
      difference_type len = last - first;
      if (len > 0) {
        value_type v = std::move(*last);
        *last = std::move(*first);
        difference_type p = 0;
        for (difference_type c = 1; c < len; c = p * 2 + 1) {
          if (c + 1 < len && comp(first[c], first[c + 1]))
            ++c;
          if (!bool(comp(v, first[c])))
            break;
          first[p] = std::move(first[c]);
          p = c;
        }
        first[p] = std::move(v);
      }
    }
    

    参照