最終更新日時(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);
}

参照