GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing cpprefjp.github.io — std::pop_heap - cpprefjp C++日本語リファレンス

最終更新日時: 2026年08月25日 12時11分17秒 (JST)
Akira Takahashi が更新

function template

std::pop_heap

namespace std {
  template <class RandomAccessIterator>
  void pop_heap(RandomAccessIterator first,
                RandomAccessIterator last);           // (1) C++98

  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++98

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

概要

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

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

RandomAccessIterator は ValueSwappable の要件を満たしていること
*first の型は MoveConstructible と MoveAssignable の要件を満たしていること

事前条件

[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);
  }
}

参照

P0879R0 Constexpr for swap and swap related functions

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

std::pop_heap

概要

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

事前条件

効果

戻り値

計算量

例

出力

実装例

関連項目

参照